字符串模式匹配

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置

主要有下面两种算法：

朴素模式匹配算法

朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串匹配对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。
最多对比n-m+1个子串。
运行步骤

通过数组下标实现朴素模式匹配算法

若当前⼦串匹配失败，则主串指针 i 指向下⼀个⼦串的第⼀个位置，模式串指针 j 回到模式串的第⼀个位置
若 j > T.length，则当前⼦串匹配成功，返回当前⼦串第⼀个字符的位置 —— i - T.length
定位操作

代码实现

int Index(SString S, SString T){
    int i=1,j=1;
    while(i <= S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            ++i;
            ++j;    //继续比较后继字符
        }
        else{
            i=i-j+2;
            j=1;    //指针后退重新开始匹配
        }
    }
    if(j > T.length)
        return i-T.length;
    else
        return 0;
}

复杂度分析

设主串⻓度为 n，模式串⻓度为 m，则
最坏时间复杂度 = O(nm)
最好时间复杂度 = O(n)
最坏时间复杂度O(nm)

最坏的情况，每个⼦串都要对⽐ m 个字符，共 n-m+1 个⼦串，复杂度 = O((n-m+1)m) = O(nm)
注：很多时候，n >> m
最好时间复杂度O(n)

最好的情况，每个⼦串的第⼀个字符就匹配失败，共 n-m+1 个⼦串，复杂度 = O(n-m+1) = O(n)
注：很多时候，n >> m

总结