1 #include<bits/stdc++.h> 2 #define N 1000000 3 using namespace std; 4 typedef long long ll; 5 char s[N],t[N]; 6 int next[N]; 7 int slen,tlen; 8 void getnext(){ 9     int i=0,j=-1;//注意写next数组时j为-1 10     next[0]=-1;11     while(i<tlen){12         if(j==-1||t[i]==t[j]) next[++i]=++j;13         else j=next[j];14     }15 }16 int kmp_index(){17     getnext();18     int i=0,j=0;19     while(i<slen&&j<tlen){20         if(j==-1||s[i]==t[j]) i++,j++;21         else j=next[j];22     }23     if(j==tlen) return i-j;24     else return -1;25 }