/*KMP算法*/
#include <stdio.h>
#include <math.h>

#include <string.h>
int main(void)
{
	int next[128];
	next[0]=0;
	char T[128];
	char S[128];
	int i,j,lenT,lenS;
	
	printf("请输入主串：");
	gets(T);
	printf("请输入模式串：");
    gets(S);
	
	i=1;
	j=0;
	lenT=strlen(T);
	lenS=strlen(S);
	while(i<lenS)
	{
		if(S[i]==S[j])
			next[i++]=++j;
		else
		{
			if(j>0)
				j=next[j];
			else
			{
				next[i]=0;
				i++;
			}		
		}	
	}
	i=0;j=0;
	while(i<lenT&&j<lenS)
	{
		if(T[i]==S[j])
		{
			i++;j++;
		}
		else
		{
			if(j>0)
				j=next[j];
			else
				i++;	
		}
	}
	if(j=strlen(S)-1)
	{	printf("%d",i-j);}
	else
		printf("无匹配字符串！");
		
	return 0;		
}