浅谈KMP

· · 题解

问题的引入

今天我们来了解一下kmp字符匹配算法

首先来看一道经典题目（Link）

第一眼看到会考虑使用暴力算法：

那么此时黑框内的皆为失配情况且存在过多不必要的情况，且时间复杂度为:O(nm)

所以考虑引进法2：kmp大法

kmp过程


可见字符串在p[4]处失配，就在匹配的部分中寻找如蓝色部分的1==2==3的字符，下一次就可以直接将1挪到2处，减少重复剩余的运算。这个过程中，我们需要移动p字符串的位置那么我们就需要一个kmp数组（本人常写作next数组） 下面我们引入正题：

求解next数组的值

说到next数组我们就不得不引出一个表格

next数组就是上表的第3列

先解释一下公共前后缀

ABAB的前缀：A,AB,ABA,ABAB
ABAB的后缀：B,AB,BAB,ABAB

显然，此处有两组相同的前后缀，但因为“ABAB”这一项没有研究价值，所以最长的公共前后缀长度为2

其次，求next数组，可以理解为将自己与自己进行kmp操作所以很容易得到代码：

void getnext(){//处理模式串的next值,将自己与自己进行KMP 
    mynext[0] = 0;
    int j = 0;
    for(int i=1;i<p.length();i++){//遍历整个字符串 
        while(j>0/*(j<0时不合法)*/ && p[i]!=p[j]){
            j = mynext[j-1];//当字符串失配时将j回退 
        }
        if(j==0){
            if(p[i]==p[j]){
                j++;
            }else{
                j=0;
            }
        }else{
            j++;
        } 
        mynext[i] = j;
    }
}

求出问题的解

如果你看到了这里，那么你已经迈过了最难的一道坎 下面我们来讲如何求出问题的解

首先，getnext()是让模式串与自己进行kmp,那么kmp()是将模式串与文本串进行kmp。同理，可得出代码:

    cnt = 0;
    int j = 0;
    for(int i=0;i<t.length();i++){//遍历整个字符串 
        while(j>0/*j<0时不合法*/ and t[i]!=p[j]){
            j = mynext[j-1];//当字符串失配时将j回退 
        }
        if(j==0){
            if(t[i]==p[j]){//匹配为1 
                j++;cnt = 1;
            }else{
                cnt = 0;//失配为0 
            }
        }else{
            cnt = j+1;j++;
        }
        if(cnt == p.length()) cout << i-p.length()+1+1 << endl;//i从0开始 
    }

求时间复杂度

那么，暴力算法是 O(nm)的时间复杂度 在上面的kmp中getnext是 O(n) kmp是O(m) 最终时间复杂度是O(n+m)

结束收工

完美撒花qwq