洛谷P3375KMP字符串匹配

传送门

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define re register
using namespace std;
const int maxn = 1000005;inline long long read() {
char ch = getchar();
long long f = 1 , x = 0;
while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ;ch = getchar();}
while(ch >= '0' && ch <= '9') {x = (x << 1) + ( x << 3) + ch - '0';ch = getchar();}
return x * f;
}char s1[maxn],s2[maxn];
int len1,len2;
int nxt[maxn];
//用于记录当匹配到模式串的第 i 位之后失配,该跳转到模式串的哪个位置int main(){
cin >> s1 + 1 >> s2 + 1 ;
len1 = strlen(s1 + 1) , len2 = strlen(s2 + 1);
nxt[0] = nxt[1] = 0;
int j ;//j可以看做表示当前已经匹配完的模式串的最后一位的位置
for(re int i = 2 ; i <= len2 ; ++i) {
while(j && s2[i] != s2[j + 1])  j = nxt[j];
//如果失配 ，那么就不断向回跳，直到可以继续匹配
if(s2[j + 1] == s2[i])  j++;
//如果匹配成功，那么对应的模式串位置++
nxt[i] = j ;
}
j = 0;
for(re int i = 1 ; i <= len1 ; ++i) {
while(j && s2[j + 1] != s1[i]) j = nxt[j];
//此处判断j是否为0的原因在于，如果回跳到第一个字符就不 用再回跳
if(s2[j + 1] == s1[i])  j++ ;
if(j == len2) {
printf("%d\n",i - len2 + 1) ;
j = nxt[j];
}
}
for(re int i = 1 ; i <= len2 ; ++i)
printf("%d " , nxt[i]);
return 0;
}