#include<iostream.h>
#include<string.h>
//失效函數
int *f(char *strshort)
{
	int length=strlen(strshort);
	int *array=new int[length];
	array[0]=-1;
	for(int j=1;j<length;j++)
	{
		int i=array[j-1];
		while(strshort[j]!=strshort[i+1]&&i>=0)
			i=array[i];
		if(strshort[j]==strshort[i+1])
			array[j]=i+1;
		else array[j]=-1;
	}
	return array;
}
//KMP算法
int kmp_find(char *strlong,char *strshort)
{
	int len1=strlen(strlong),len2=strlen(strshort);
	int i=0,j=0;
	int *ff=f(strshort);
	while(i<len1&&j<len2)
		if(strlong[i]==strshort[j])
		{
			i++;j++;
		}
		else if(j==0)
			i++;
			else j=ff[j-1]+1;
	if(j==len2) return i-len2;
	else return -1;
}

void main()
{
	char a[50],b[30];
	cout <<"input two strings:\n";
	cout<<"the original:";
	cin>>a;
	cout<<"the substring:";
	cin>>b;
	int result=kmp_find(a,b);
	if(result==-1)
		cout<<"can't find!\n";
	else cout <<"the position:"<<result+1<<endl;
}