给你两个字符串A，B，请输出B字符串在A字符串中出现了几次。

多组测试数据，每组输入两个字符串。字符串的长度 <= 1000000.

输出B在A中出现的次数。

aaa aa

1

*qi

#include <cstdio>

 #include <cstring>

 const int N =  + ;

 char s[N],t[N];

 int lens,lent;

 int next[N];

 void get_fail() {

     next[] = -;

     for (int i = ,j = -; i < lent; ++ i) {

         while (j != - && t[i] != t[j+]) j = next[j];

         next[i] = t[i] == t[j+] ? ++ j : j ;

     }

 }

 int work() {

     lens = strlen(s);

     lent = strlen(t);

     get_fail();

     int ret = ;

     for (int i = ,j = -; i < lens; ++ i) {

         while (j != - && s[i] != t[j+]) j = next[j];

         if (s[i] == t[j+]) {

             ++ j;

             if (j == lent-) {

                 j = -;

                 ret ++;

             }

         }

     }

     return ret;

 }

 int main() {

    // freopen ("a.txt" , "r" , stdin ) ;

     while (scanf("%s",s) != EOF) {

         scanf("%s",t);

         printf("%d\n",work());

     }

     return ;

 }

kmp , 用来求串的匹配度，复杂度O（n）

这道题是我的kmp入门题，所以带上心得：

这里是一个很经典的介绍。

我觉得Partial match table就是为匹配串的每个字母找周期。

t[0]    t[1]    t[2]    t[3]    t[4]

a        b       c         a       a

-1       -1      -1      0      -1

之所以t[3]的nxt[3] = 0 , 是因为它与t[0] 构成周期 （t[3] = t[0]嘛） ；

而nxt[4] = -1 , 是以为它和t[1] 不构成周期 （t[4] != t[1]) ;

而之所以这么搞，是为了在t[3]找失败时能直接从最近的一个循环上继续下去 ， 而不是暴力的让文本串重新开始找

kmp的nxt[]数组进一步：http://www.cnblogs.com/*qi/archive/2012/01/06/2314078.html

看过上面的连接后，我们已经可以求出字符串的最小周期了。但进一步，如何求出该字符串所有周期呢

#include<bits/stdc++.h>

using namespace std ;

void get_nxt () {

    .....

}

int main () {

    scanf ("%s" , s) ;

    lens = strlen (s) ;

    get_nxt () ;

    for (int i = nxt[lens-] ; ~i ; i = nxt[i]) {

        printf ("%d\n" , lens--i ) ;

    }
　　　printf ("%d\n" , lens）；//毫无疑问，lens本身也是周期

    return  ;

}

至于证明和链接中岐哥的证明一模一样。