学步园

题目链接:   poj 3461

题目大意:   给出主串和模式串，求模式串在主串中出现的次数(部分可以重合)

解题思路:   KMP从主串的第一个字符开始匹配

                   开始是匹配成功就立刻退出，再次从上次退出的下一个字符开始匹配，TLE...

                   利用上next[ ]数组的含义，每次不全部退出，而是退出部分j=next[ j ]

代码:

//Final    Kmp，给出模式串和主串，求模式串在主串中出现的次数(可以部分重叠)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 10010
int Tlen,TTlen,End,next[MAX];
char ch[MAX*100],chT[MAX];

void Get_next()
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<=Tlen)
	{
		if(j==-1||chT[i]==chT[j])
		{
			i++; j++;
			next[i]=j;
		}
		else 
			j=next[j];
	}
}

int Kmp(int u)
{
	int i=u-1,j=-1,m=0;     //字符串从0开始存储的
	while(i<=TTlen)
	{
		if(j==-1||ch[i]==chT[j])
		{
			i++; j++;
		}
		else
			j=next[j];
		if(j>=Tlen)         //**注意这里要j--,i++,因为上面匹配成功了i和j的值加多了1
		{
			m++;
			j--; i--;
			j=next[j];      //返回
		}
	}
	return m;
}

int main()
{
	int n,m,k,i;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s%s",chT,ch);
		memset(next,0,sizeof(next));
		Tlen=strlen(chT);
		TTlen=strlen(ch);
		Get_next();
		k=Kmp(0);      //Kmp从第一个字符开始匹配
		printf("%d\n",k);
	}
	return 0;
}