标签：int s2 s1 ret 板子 ++ KMP pi
P3426
#include <cstdio>
#include <cstring>
#include <vector>
#define sd std::
namespace m{ // }
constexpr int LEN = 1e6;
sd vector<int> prepare(char* a){
int len = strlen(a);
sd vector<int> ret(len);
for(int i=1; a[i]; ++i){
int j = ret[i-1];
while(j && a[i] != a[j]) j = ret[j-1];
if(a[i] == a[j]) ++j;
ret[i] = j;
}
return ret;
}
char s1[LEN+1], s2[LEN+1];
void work(){
scanf("%s%s", s1, s2);
auto pi = prepare(s2);
int len2 = strlen(s2);
int j = 0;
for(int i=0; s1[i]; ++i){
while(j && s1[i] != s2[j]) j = pi[j-1];
if(s1[i] == s2[j]) ++j;
if(j == len2) printf("%d\n", i-len2+2), j = pi[j-1];
}
for(int i:pi){
printf("%d ", i);
}
}
} int main(){m::work(); return 0;}
标签：int,
s2,
s1,
ret,
板子,
++,
KMP,
pi
From： https://www.cnblogs.com/x383494/p/17367663.html