分析
nxt[i]=len
表示以i结尾的字符串str[1..i]中
前缀 prefix[1..len]==suffix[i-len+1,i]条件下最大长度是len
c++
#include <iostream>
#include <cstring>
namespace alg_{
typedef const char* sptr;
//idx from 1
void kmp_search(sptr txt,int txt_len,sptr word,int word_len){
bool matched=false;
int nxt[word_len];
memset(nxt,0,sizeof(nxt));
//get nxt[]
int j=0;//反复扫描短词所用的下标
for(int i=2;i<=word_len;i++){
while(j&&word[i]!=word[j+1]) j=nxt[j];//not match, go back
if(word[i]==word[j+1]) j++;//same, go forward
nxt[i]=j;
}
//matching
j=0;
for(int i=1;i<=txt_len;i++){
while(j&&txt[i]!=word[j+1]) j=nxt[j];
if(txt[i]==word[j+1]) j++;
if(j==word_len){
printf("%d ",i-word_len);
matched=true;
j=nxt[j];
}
}
matched ? printf("\n") : printf("can't match.\n");
}
}
const int N=1000010;//bigger
char p[N],s[N];
int n,m;
int main(){
std::cin>>n>>p+1>>m>>s+1;
alg_::kmp_search(s,m,p,n);
return 0;
}