本题就是给出非常多对字符串，然后问一个字符串在另外一个字符串出现的次数。

就是所谓的Strstr函数啦。

Leetcode有这道差点儿一模一样的题目。

使用KMP算法加速。算法高手必会的算法了。

另外看见讨论说什么使用KMP还超时，最大可能是没有真正理解next table的含义，写了错误的代码，故此尽管自己执行结果正确，可是却没有真正发挥next table的作用。使得算法退化为暴力法了，所以执行正确，但超时。

KMP參考： http://blog.csdn.net/kenden23/article/details/14178121

#include <stdio.h>

#include <string.h>

const int MAX_N = 10001;

const int MAX_T = 1000001;

char word[MAX_N];

char text[MAX_T];

int nextTbl[MAX_N];

int wn, tn;

int getTimes()

{

	int ans = 0;

	int i = 0, j = 0;	//i为text的当前下标，j为word的当前下标

	for (; i-j <= tn-wn; i++)

	{

		if (text[i] == word[j])

		{

			j++;

			if (j == wn)

			{

				ans++;

				j = nextTbl[j-1];

			}

		}

		else if (j > 0)

		{

			j = nextTbl[j-1];

			i--;

		}

	}

	return ans;

}

void genTbl()

{

	memset(nextTbl, 0, sizeof(int) * (wn));

	int i = 1, j = 0;

	while (i < wn)

	{

		if (word[i] == word[j]) nextTbl[i++] = ++j;

		else if (j > 0) j = nextTbl[j-1];

		else i++;

	}

}

int main()

{

	int T;

	scanf("%d", &T);

	getchar();

	while (T--)

	{

		gets(word);//fgets(word, MAX_N, stdin);//fgets会在末尾保留'\n'

		gets(text);//fgets(text, MAX_T, stdin);

		wn = strlen(word);

		tn = strlen(text);

		genTbl();

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

	}

	return 0;

}