KMP算法

作用：将原本暴力查找子串的时间复杂度由 O(m×n)O_{(m\times n)} 降为接近 O(n)O_{(n)}

实现：

  • 创建子串的下标转移索引
    1. 首先模板字符串的0号位置后面不能构成后缀故不存在下标转移，故置为-1
    2. 模板字符串的焦点已近移动到了第 i−1i-1 位且成功匹配了长度为 jj 的前缀，即确认了 p[0 ~ j-1] 与 p[i-j ~ i-1] 完全匹配后
    3. 如果模板字符串的第 ii 位与第 jj 位匹配，则说明当前匹配字符串可以加1
    4. 如果不匹配，则需要将当前位置不能匹配更长的子串了需要将匹配长度缩短，这时可以使用已经建立好的匹配下标索引转移 ne[j] 即可确定缩短后的匹配字符串可以最大匹配
    5. 此时重复步骤3-4直到匹配可以确认p[i]的匹配长度或者当前无法找到匹配的子串即匹配长度为-1
  • 查找子串
    1. 此时只需要将匹配的字符串从原来的模板字符串转化为目标字符串即可

1055_48986c551c-kmp2

代码：

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
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 100010, M =1000010;
int n, m;
char p[N], s[M];
int ne[N];

int main(){
    cin>>n>>p>>m>>s;
    
    ne[0] = -1;
    for(int i = 1, j = -1; i < n; i++){
        while(~j && p[i] != p[j+1]) j = ne[j];
        if(p[i] == p[j+1]) j++;
        ne[i] = j;
    }
    
    for(int i = 0, j = -1; i < m; i++){
        while(~j && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) j++;
        if(j == n-1){
            cout<<i-n+1<<" ";
            j = ne[j];
        }
    }
    
    return 0;
}