KMP模式匹配 三（弦）

原文请訪问我的博客：xiaoshig.sinaapp.com

KMP模式匹配 三（串）

Time Limit:1000MS     Memory Limit:131072KB     64bit IO Format:%lld & %llu

Submit Status

Description

输入一个主串和一个子串，若匹配成功，则找出匹配的趟数和在子串在主串中的位置，若匹配不成功，则输出0

Input

输入两个字符串

Output

输出匹配的趟数和位置

Sample Input

ababcabcacbab
abcac

Sample Output

3 6

#include<iostream>
#include<cstring>
using namespace std;
int a[100000];
char c[10000];
char b[100000];
int main()
{
	int j,n,i,k;
	cin>>c;
	cin>>b;

	a[0]=-1;

	j=-1;
	i=0;
while(b[i]!='')
{
	if(j==-1||b[j]==b[i])
	{
		j++;i++;
	//	if(b[i]!=b[j])
			a[i]=j;
	//	else
	//	{if(a[j]==-1)
	//	a[i]=0;
	//	else
	//		a[i]=a[j];}
	}
	else j=a[j];
}
i=0;
j=0;k=0;n=1;
while(c[i]!='')
{
if(c[i]==b[j])
{i++;j++;if(b[j]==''){k=1;break;}}
else if(a[j]==-1){i++;j=0;n++;}
else {j=a[j];n++;}
}
i=i-strlen(b)+1;
if(k==0)
cout<<-1<<endl;

else cout<<n<<' '<<i<<endl;
return 0;
}

版权声明：本文博主原创文章，博客，未经同意不得转载。