前言

狗屁不是，建议别看！！！

题目链接

P3375 【模板】KMP 字符串匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析

先给个例子

s1：ABCABCABB

s2：ABCABB

若使用朴素算法匹配，当匹配到

s1：ABCAB C ABB

s2：ABCAB B

时，朴素算法会跳出，然后匹配下一位。

最终匹配到

s1：ABC ABCABB

s2：    ABCABB

匹配成功

我们发现其中

s1：ABC AB CABB

s2：    AB CABB

AB二位在第一次匹配中已经匹配过了

那么如何简化该重复操作呢？

定义next数组（next是关键字，不要用作变量名）

next[i]表示的是s2在i之前的最长的完全相同的前缀后缀长度（不能为整个字符串）

例如：ABCAB

前缀有A、AB、ABC、ABCA

后缀有B、AB、CAB、BCAB

最长的完全相同的前缀后缀为AB，所以next=2

回到第一次匹配中，当匹配到

s1：ABCAB C ABB

s2：ABCAB B

时，即指针i（s1）=6，指针j（s2）=6；

由于next[5]=2，即s2中末尾AB（4，5）与开头AB（1，2）是等价的，并且s2末尾AB与s1中间的AB（4，5）是等价的

所以s1中间的AB可以与s2开头的AB匹配且最长

满足最长即前面的B、C都无法完成匹配

令此时j=next[j-1]+1，再进行下一次匹配

直到j=6（len s2）时匹配结束

那么如何计算next呢？

令i为当前所计算字符串的末尾，j为前缀的末尾

与两个字符串匹配类似

当a[i]!=a[j]时 令j=next[j-1]+1

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=1000006;
 5 
 6 char a[N],b[N];
 7 int ne[N];
 8 
 9 int main(){
10     scanf("%s %s", a+1, b+1);
11     int an=strlen(a+1),bn=strlen(b+1);
12     int j=0;//i，j指需要匹配的字符的前一个值
13     for(int i=1;i<bn;i++){
14         while(j>0&&b[j+1]!=b[i+1]) j=ne[j];
15         if(b[j+1]==b[i+1]) j++,ne[i+1]=j;
16     }
17     j=0;
18     for(int i=0;i<an;i++){
19         while(j>0&&b[j+1]!=a[i+1]) j=ne[j];
20         if(b[j+1]==a[i+1]) j++;
21         if(j==bn){
22             printf("%d\n", i+1-bn+1);
23             j=ne[j];
24         }
25     }
26     for(int i=1;i<=bn;i++) cout<<ne[i]<<" ";
27     return 0;
28 }