2296: KMP模式匹配 二(串)
时间限制: 1 Sec 内存限制: 128 MB
提交: 29 解决: 17
题目描述
输入一个主串和一个子串,用KMP进行匹配,问进行几趟匹配才成功,若没成功,则输出0
输入
输入一个主串和一个子串
输出
匹配的趟数
样例输入
ababcabcacbab
abcac
样例输出
3
迷失在幽谷中的鸟儿,独自飞翔在这偌大的天地间,却不知自己该飞往何方…
#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 i=0,j=0,ci=1;
while(i<s.length&&j<t.length)
{
if(j==-1||s.data[i]==t.data[j]) //模式串和主串对应字符匹配成功
{
i++;j++;
}
else j=next[j],ci++; //模式串指针回到相应next,匹配次数+1
}
if(j>=t.length)return ci;
else return 0;
}
int main()
{
SqString s,t;
int next[SizeMax]={-1};
char c[SizeMax],d[SizeMax];
gets(c);
gets(d);
StrAssign(s,c); //建立串
StrAssign(t,d);
getnext(t,next); //得到next值
int ci=kmp(s,t,next); //得到匹配到的位置
printf("%d\n",ci);
return 0;
}