数据结构(C语言版)严蔚敏(字符串的模式匹配算法--KMP算法)

数据结构(C语言版)严蔚敏(字符串的模式匹配算法–KMP算法)

1.暴力匹配算法

// 暴力匹配算法
int Index2(SString S,SString T)
{
    // S是主串，T是子串
    int i=0,j=0;
    while(i<S.length&&j<T.length){
        if(S.ch[i]==T.ch[j]){
            i++;
            j++;
        }
        else{
            i=i-j+1;
            j=0;
        }
    }
    if(j>=T.length)
        return i-T.length+1;
    else
        return 0;
}

运行结果：

最坏时间复杂度为：O(nm)，其中n和m分别代表主串和模式串的长度。

2.KMP算法

KMP算法(用空间来换时间，需要提前计算子串部分匹配值)
1.字符串的前缀、后缀和部分匹配值
前缀指除最后一个字符以外，字符串的所有头部子串；后缀指除第一个字符外，字符串的所有尾部子串；部分匹配值则是字符串的前缀和后缀的最长且相等前后缀长度。

如子串"ababa"

"a"的前缀和后缀都为空，最长相等前后缀长度为0
"ab"的前缀{"a"},后缀为{"b"}，最长相等前后缀长度为0
"aba"的前缀{"a","ab"}，后缀为{"ba","a"}，最长相等前后缀长度为1
"abab"的前缀{"a","ab","aba"},后缀为{"bab","ab","b"},最长相等前后缀的长度为2
"ababa"的前缀{"a","ab","aba","abab"},后缀为{"baba","aba","ba","a"},最长相等前后缀的长度为3

字符串”ababa“的部分匹配值为00123

用同样的方式可以得到字符串”abcac“的部分匹配值为：00010

PM表
用PM表来进行字符串匹配
移动位数=已匹配的字符数-对应的部分匹配值

1
主串 a b a b c a b c a c
子串 a b c
第1次匹配‘a’与‘c’不等，查PM表可知最后一个字符‘b’对应的部分匹配值为0，子串移动位数为：2
2
主串 a b a b c a b c a c
子串     a b c a c
第2次匹配‘b’与‘c’不等，查PM表可知最后一个字符‘a’对应的部分匹配值为1，子串移动位数为：4-1=3
3
主串 a b a b c a b c a c
子串           a b c a c
匹配成功！

KMP算法时间复杂度为O(n+m)
KMP算法的改进
移动位数=已匹配的字符数-对应的部分匹配值
如果用j表示子串的字符下标，则上述公式可以写成Move=（j-1）-PM[j-1]
使用部分匹配值时，每当碰到匹配失败时，都需要去找它前一个元素的部分匹配值，为了方便，改进PM表如下：

上述公式可以写成：Move=（j-1）-next[j]
相当于子串的比较指针j回退到 j=j-Move=next[j]+1
于是，上述next数组进一步可以表示为：

最终得到子串指针变化公式为j = next[j]
next[j]的含义：在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较。
参考代码如下：

void get_next(SString T,int next[]){
    int i=1,j=0;
    next[1] = 0;
    while(i<T.length){
        if(j==0 || T.ch[i-1] == T.ch[j-1]){
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

int Index_KMP(SString S,SString T,int next[]){
    int i=1,j=1;
    while(i<=S.length&&j<=T.length){
        if(j==0||S.ch[i-1]==T.ch[j-1]){
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}

第一个函数用于求next数组，第二个函数就是KMP匹配算法，运行结果同上。