原文请訪问我的博客：

KMP模式匹配 三（串）

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

 

Description

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

Input

输入两个字符串

Output

输出匹配的趟数和位置

Sample Input

ababcabcacbababcac

Sample Output

3 6

#include
        
         #include
         
          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]!='\0'){	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]!='\0'){if(c[i]==b[j]){i++;j++;if(b[j]=='\0'){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<
         
        

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