#include
     
      #include
      
       #include
       
        #define sz 1000010using namespace std;int fail[sz];char a[sz], b[sz];inline void init(int n) {    int j = 0;    fail[1] = 0;    for(int i = 2; i <= n; i++) {        while(j>0 && b[i] != b[j+1]) j = fail[j];        if(b[i] == b[j+1]) j++;        fail[i] = j;    }}inline void match(int n, int m) {    int j = 0;    for(int i = 1; i <= n; i++) {        while(j>0 && a[i] != b[j+1]) j = fail[j];        if(a[i] == b[j+1]) j++;        if(j == m) printf("%d\n",i-m+1), j = fail[j];    }}inline void print(int n) {    for(int i = 1; i <= n; i++) printf("%d ",fail[i]);}int main() {    scanf("%s%s",a+1, b+1);    int lena = strlen(a+1), lenb = strlen(b+1);    init(lenb); match(lena, lenb); print(lenb);    return 0;}
       
      
     

 我学了一下午kmp，结果某人说noip考的字符串匹配hash就可以搞定QAQ