前言：

昨天不小心玩嗨了，不想更新，坚持了快两个星期的好习惯就这样没了，我对自己真的好失望啊。

言归正传，今日复习了KMP算法，一种解决主串的模式定位问题，比如解决一个主串中是否有另外一个副串。

概述:

kmp算法主要分为两个部分:1.预处理next数组，2.匹配主子串

预处理next数组

kmp与暴力最大的不同在于kmp会根据之前匹配的数据进行处理，以便后面的匹配。

kmp预处理next数组原理上是记录相同的前后缀，并用next数组记录前缀（遍历的时候指针是在后缀）

而自己跟自己匹配就是找相同前后缀

1
2
3
4
5
6
7
8
9
for(int i=2,j=0;i<=lb;i++){
    while(j&&b[i]!=b[j+1]){
        j=ne[j];
    }
    if(b[i]==b[j+1]){
        j++;
    }
    ne[i]=j;
}

匹配主子串

让主子串进行匹配，如果主串某一位置不匹配子串某一位置，子串从后缀跳到前缀（因为不匹配的前面所以的部分子串与主串相同）

如果子串走到了子串终点，说明主串中有子串，则子串继续跳到前缀，继续匹配主串，观察是否还有符合子串部分。

1
2
3
4
5
6
7
8
9
10
11
for(int i=1,j=0;i<=la;i++){
    while(j&&a[i]!=b[j+1]){
        j=ne[j];
    }
    if(a[i]==b[j+1]){
        j++
    }
    if(j==lb){
        j=ne[j];
    }
}

实践

题目：KMP字符串匹配

给出两个字符串s1和s2，若s1的区间[l,r]子串与s2完全相同，则s2在s1中出现了，其出现的位置为l。
现在请你求出s2在s1中所有出现的位置

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int la,lb,ne[N];
char a[N],b[N];
int main(){
    cin>>a+1>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for(int i=2,j=0;i<=lb;i++){
        while(j&&b[i]!=b[j+1]){
            j=ne[j];
        }
        if(b[i]==b[j+1]){
            j++;
        }
        ne[i]=j;
    }
    for(int i=1,j=0;i<=la;i++){
        while(j&&a[i]!=b[j+1]){
            j=ne[j];
        }
        if(a[i]==b[j+1]){
            j++;
        }
        if(j==lb){
            cout<<i-j+1<<endl;
            j=ne[j];
        }
    }
    for(int i=1;i<=lb;i++){
        cout<<ne[i]<<" ";
    }
    return 0;
}