上午我用了Rabin-Karp算法做的。基本的数据可以测试通过，但是一提交就WA。偶滴天啊，我不知道错在哪啊。。我是非专业的。。呜呜。找了半天找不出。算了。看人家都是用KMP做的，那我下午就用KMP写一个吧。一定把它拿下！！哼哼

   Rabin-Karp:

#include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; #define M 16381*4733+1 int nCount; void Rabin_Karp(char*T,char* W,int d,int q ) {
   //搜索W在T中的位置 //参数d：字母表的进制，即字母表的元素个数 //参数q：一个比较大的素数，只需d*q
        
       
      
     

 

KMP: AC的。

#include 
     
       #include 
      
        #include 
       
         using namespace std; #define N 10001 #define M 1000001 int next[N]; int nCount; void get_next(char* str) {
   int i=0,j=-1,len=strlen(str);     next[i]=j; while(i
        
         =0 && str[i]!=str[j]) j=next[j];         i++;j++;         next[i]=j;     } } void kmp_search(char *T,char *W) {
   int i=0,j=0,len1=strlen(T),len2=strlen(W); while(i
         
          =0 && T[i]!=W[j]) j=next[j];         i++;j++; if(j==len2)         {
             nCount++;           j=next[j];         }     } } int main() {
   int n; char W[N]; char T[M];     freopen("acm.txt","r",stdin);     scanf("%d",&n);     getchar(); while(n--)     {
           scanf("%s",W);             scanf("%s",T);            memset(next,0,sizeof(next));         nCount=0;         get_next(W);         kmp_search(T,W);             printf("%d\n",nCount);     }    return 0; }