KMP算法
模式串p:就是需要寻找的那个串
文本串t:就是一个待与模式串p匹配的字符串
作用:
1.求出模式串p在文本串中出现的位置
2.求出模式串长度为i的前缀的最长的border(就是nxt[]数组，获取失配指针的数组)
算法思想:
充分利用模式串p，使得之前被匹配过的地方不再多匹配
与文本串匹配时，失配之后，利用某一部分前缀快速移动
nxt[i]数组记录匹配到模式串的第i位之后失配,该跳转到模式串的哪个位置，
那么对于模式串的第一位和第二位而言，只能回跳到1
//luoguP3375 KMP字符串匹配
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int nxt[N];
void getfail(char *p) {
int m=strlen(p+1),j=0;
nxt[0]=0;
nxt[1]=0;
for(int i=2;i<=m;i++) {
while(j&&p[i]!=p[j+1]) j=nxt[j];
if(p[i]==p[j+1]) j++;
nxt[i]=j;
}
}
void kmp(char *t,char *p) {
int n=strlen(t+1);
int m=strlen(p+1);
getfail(p);
int j=0;
for(int i=1;i<=n;i++) {
while(j&&t[i]!=p[j+1]) j=nxt[j];
if(t[i]==p[j+1]) j++;
if(j==m) {
printf("%d\n",i+1-m);
j=nxt[j];
}
}
}
char p[N],t[N];
int main() {
cin>>(t+1)>>(p+1);
kmp(t,p);
int m=strlen(p+1);
for(int i=1;i<=m;i++) {
printf("%d ",nxt[i]);
}
return 0;
}