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

代码如下：

#include<cstdio>//poj 3461 kmp

#include<cstring>

using namespace std;

char s1[1000005], s2[10005];

int len1, len2,next[10005];

void getnext()

{   //next数组其实是：当前字符匹配失败时，小字符串退回到合适的位置，然后继续匹配。

    int i = 0, j = -1;

    next[0] = -1;

    while(i<len2)

    {

        if(j==-1 || s2[i]==s2[j])//如果没有前缀或 前缀等于后缀，则进入

        {

            i++; j++; //先自增1

            if(s2[i]==s2[j])  //如果继续相等，则next[i]为当j不匹配又退回的合适位置。

                next[i] = next[j];

            else  //如果不相等，则next[i]就等于j

                next[i] = j;

        }

        else j = next[j];

    }

}

int kmp()

{

    int sum = 0, i = 0, j = 0;

    getnext();

    while(i<len1)  //i只会增加（线性），而j会回溯反复进行匹配

    {	/*当j=-1时，表明上一次连第一个字符都不相等，则i会继续前进，j经过回溯又前进，还是变为第一个字符。

	      下次循环继续匹配第一个字符*/

        if(j==-1 || s1[i]==s2[j])

        {

            i++; j++;

            if(j==len2)

            {

                sum++;

                j = next[j];

            }

        }

	/*如果当前字符不匹配，i不变，等待下一个匹配。而j退回到合适的位置。

	  下次循环继续与当前i进行匹配*/

        else j = next[j];

    }

    return sum;

}

int main()

{

    int T;

    scanf("%d\n",&T);

    while(T--)

    {

        scanf("%s%s",s2,s1);

        len1 = strlen(s1); len2 = strlen(s2);

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

    }

    return 0;

}