KMP模版,网上找到的,有时间我自己写个吧~预计在2天之内。算法导论不好懂啊!!!先用着吧,这个还是比较慢。
--------------------------------------------------------------------------------------------------------------------
#include <iostream> #include <cstdio> #include <string> using namespace std; const int N = 1000; int sign; 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; } } 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){ sign=1;break; } } } int main(){ while( cin >> T >> P) { sign=0; COMPUTER_PREFIX_FUNCTION(P); KMP_MATCHER(T, P); if(sign==1) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }