题目链接：

　　

题目描述：

　　给出两个串，分别为a，b，问a串在b串中出现了几次？(其实位置不同，就算不同的串)

解题思路:

　　字符串匹配首选KMP算法，刚开始的时候，每次匹配成功一个子串后，我就把母串中的指针指向匹配成功的子串起始位置加一处。无疑TLE，ORZ.jpg。

　　最后想到如果子串很长的话并且出现的字符很单一，算法的复杂度就降为O(M*N)了，GG。其实把匹配到子串末位后，把当前的情况当做失配就好了，移动子串中的指针到对应的Next值处。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7  8 #define LL long long 9 #define maxn 1001010 #define mod 10000000711 12 char a[maxn*100], b[maxn];13 int Next[maxn], n, m;14 15 void Get_Next (char b[], int m)16 {17     int i, j;18     j = Next[0] = -1;19     i = 0;20 21     while (i < m)22     {23         while (j!=-1 && b[i]!=b[j])24             j = Next[j];25 26         Next[++ i] = ++ j;27     }28 }29 30 int kmp (char a[], char b[])31 {32     int ans, i, j;33     i = j = ans = 0;34 35     Get_Next (b, m);36 37     while (i < n)38     {39         while (j!=-1 &&a[i] != b[j])40             j = Next[j];41 42         j++, i++;43 44         if (j == m)45         {46             ans ++;47             j = Next[j];///匹配成功后，当做失配，移动j到Next处48         }49     }50     return ans;51 }52 53 int main ()54 {55     int T;56     scanf ("%d", &T);57 58     while (T --)59     {60         scanf ("%s %s", b, a);61 62         n = strlen (a);63         m = strlen (b);64 65         printf("%d\n", kmp(a, b));66     }67     return 0;68 }69