image-20231213230121396

image-20231213233014666

这个时候p[i]!=p[j+1],数组不匹配时，执行j=next[j]语句，因为不匹配，这时候会让j进行后退，直到j后退到0。

kmp的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//子串和长串下标从1开始
bool kmp(char *s,int l1,char *p,int l2){
    /*求next数组*/
    for(int i=2,j=0;i<=l1;i++){
        while(j&&p[i]!=p[j+1]) j=next[j];
        if(p[i]==p[j+1]) j++;
        next[i]=j;
    }
    /*进行字符串配对*/
    for(int i=0;i<l1;i++){
        while(j<l2&&s[i]==p[j+1]) j++;
        if(j==l2){
            cout<<"匹配成功"<<endl;
            return true;
        }
        j=next[j];
    }
}