/*参考《算法导论》 My Code:*/ #include 
     
       #include 
      
        #include 
       
         using namespace std; const int N = 1000; string T, P; int pi[N]; void COMPUTER_PREFIX_FUNCTION(string P){
   int m = P.length(), i, k; for(k = pi[0] = -1, i = 1; i < m; i++){
   while(k > -1 && P[k+1] != P[i])             k = pi[k]; if(P[k+1] == P[i])             k++;         pi[i] = k;     }     cout << "COMPUTER-PREFIX-FUNCTION" << endl; for(i = 0; i < m; i++){
           cout << pi[i] << " ";     }     cout << endl << endl; } void KMP_MATCHER(string T, string P){
   int i, n, m, k;     n = T.length(); m = P.length(); for(k = -1, i = 0; i < n; i++){
   while(k > -1 && P[k+1] != T[i])    k = pi[k]; if(P[k+1] == T[i])    k++; if(k == m-1){
               cout << "Pattern occurs with shift " << i - m + 2 << endl;             k = pi[k];         }     } } int main(){
   //freopen("data.in", "r", stdin);     cin >> T >> P;     COMPUTER_PREFIX_FUNCTION(P);     KMP_MATCHER(T, P); return 0; }