题目链接：http://poj.org/problem?id=3461

统计字符串出现的次数

1 #include
     
          2 #include
      
           3 #include
       
          4 #include
        
            5 #include
         
              6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
               10 #include
              
                11 #define dinf 0x3f3f3f3f 12 typedef long long ll; 13 //const int Max=(1<<16)+10; 14 using namespace std; 15 #define SIZE 100000005 16 17 const int N = 100000005; 18 int m_next[N]; 19 char S[N],T[N]; 20 int slen, tlen; 21 22 void getNext() 23 { 24 int j, k; 25 j = 0; k = -1; m_next[0] = -1; 26 while(j < tlen) 27 if(k == -1 || T[j] == T[k]) 28 m_next[++j] = ++k; 29 else 30 k = m_next[k]; 31 32 } 33 /* 34 返回模式串T在主串S中首次出现的位置 35 返回的位置是从0开始的。 36 */ 37 int KMP_Index() 38 { 39 int i = 0, j = 0; 40 getNext(); 41 42 while(i < slen && j < tlen) 43 { 44 if(j == -1 || S[i] == T[j]) 45 { 46 i++; j++; 47 } 48 else 49 j = m_next[j]; 50 } 51 if(j == tlen) 52 return i - tlen+1; 53 else 54 return -1; 55 } 56 /* 57 返回模式串在主串S中出现的次数 58 */ 59 int KMP_Count() 60 { 61 int ans = 0; 62 int i, j = 0; 63 64 if(slen == 1 && tlen == 1) 65 { 66 if(S[0] == T[0]) 67 return 1; 68 else 69 return 0; 70 } 71 getNext(); 72 for(i = 0; i < slen; i++) 73 { 74 while(j > 0 && S[i] != T[j]) 75 j = m_next[j]; 76 if(S[i] == T[j]) 77 j++; 78 if(j == tlen) 79 { 80 ans++; 81 j = m_next[j]; 82 } 83 } 84 return ans; 85 } 86 int main() 87 { 88 89 int TT; 90 int i, cc; 91 string str; 92 cin>>TT; 93 while(TT--) 94 { 95 getchar(); 96 97 scanf("%s %s",&T,&S); 98 slen = strlen(S); 99 tlen = strlen(T);100 printf("%d\n",KMP_Count());101 102 //cout<<"模式串T在主串S中首次出现的位置是: "<