2297: KMP模式匹配 三（串）
时间限制: 1 Sec 内存限制: 128 MB
提交: 25 解决: 16
[提交][状态][讨论版]
[Edit] [TestData]
题目描述
输入一个主串和一个子串，若匹配成功，则找出匹配的趟数和在子串在主串中的位置，若匹配不成功，则输出0
输入
输入两个字符串
输出
输出匹配的趟数和位置
样例输入
ababcabcacbab
abcac
样例输出
3 6
迷失在幽谷中的鸟儿，独自飞翔在这偌大的天地间，却不知自己该飞往何方…
#include <stdio.h>
#include <string.h>
#define SizeMax 105
typedef struct
{
char data[SizeMax];
int length;
} SqString;
void getnext(SqString s,int next[])
{
int j=0,k=-1;
next[0]=-1;
while(j<s.length-1)
{
if(k==-1||s.data[j]==s.data[k])
j++,k++,next[j]=k;
else k=next[k];
}
}
void StrAssign(SqString &s,char cstr[])
{
int i;
for(i=0; i<(int)strlen(cstr); i++)
s.data[i]=cstr[i];
s.length=i;
}
int kmp(SqString s,SqString t,int next[],int &ci)
{
int i=0,j=0;
while(i<s.length&&j<t.length)
{
if(j==-1||s.data[i]==t.data[j]) //主串与模式串对应字符匹配成功
{
i++;
j++;
}
else j=next[j],ci++; //模式串指针回溯
}
if(j>=t.length)return i-t.length+1;
else return 0;
}
int main()
{
SqString s,t;
int next[SizeMax]= {-1},ci=1;
char c[SizeMax],d[SizeMax];
gets(c);
gets(d);
StrAssign(s,c); //建立串
StrAssign(t,d);
getnext(t,next); //得到next值
int k=kmp(s,t,next,ci); //solve
printf("%d %d\n",ci,k);
return 0;
}
/*
acabaabaabcacaabc
abaabcac
4 6
*/
