串结构练习——字符串匹配
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2125
题目描述
给定两个字符串string1和string2，判断string2是否为string1的子串。
输入
输入包含多组数据，每组测试数据包含两行，第一行代表string1，第二行代表string2，string1和string2中保证不出现空格。
输出
对于每组输入数据，若string2是string1的子串，则输出"YES"，否则输出"NO"。
示例输入
abc
a
123456
45
abc
ddd
示例输出
YES
YES
NO
提示
代码：
#include<string.h>
#include<iostream>
using namespace std;
char S[],T[];
int s,t,next[],nextval[];
void get_next(char T[],int next[]);//对应模式匹配算法一next函数值
void get_nextval(char T[],int nextval[]);//对应模式匹配算法二nextval函数值
int Index_KMP(char S[],char T[],int pos);//模式匹配算法一
int Index_KMP2(char S[],char T[],int pos);//模式匹配算法二
int main()
{
while(cin>>S>>T)
{
memset(next,,sizeof(next));
int i;
s=strlen(S);
t=strlen(T);
for(i=s;i>=;i--)
S[i]=S[i-];
S[s+]='\0';
for(i=t;i>=;i--)
T[i]=T[i-];
T[t+]='\0';
//get_next(T,next);
get_nextval(T,nextval);
//int flag=Index_KMP(S,T,1);//通过这里可以验证两个算法
int flag=Index_KMP2(S,T,);
//for(i=1;i<=t;i++)
// cout<<nextval[i]<<" ";
//cout<<endl;
if(flag==)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return ;
}
void get_next(char T[],int next[])//对应模式匹配算法一next函数值
{
int i=,j=;
next[]=;
while(i<t)
{
if(j==||T[i]==T[j])
{
++i;
++j;
next[i]=j;
}
else j=next[j];
}
}
void get_nextval(char T[],int nextval[])//对应模式匹配算法二nextval函数值
{
int i=,j=;
nextval[]=;
while(i<t)
{
if(j==||T[i]==T[j])
{
++i;
++j;
if(T[i]!=T[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}
int Index_KMP(char S[],char T[],int pos)//模式匹配算法一
{
int i=pos,j=;
while(i<=s&&j<=t)
{
if(j==||S[i]==T[j])
{
++i;
++j;
}
else j=next[j];
}
if(j>t)return i-t;
else return ;
}
int Index_KMP2(char S[],char T[],int pos)//模式匹配算法二
{
int i=pos,j=;
while(i<=s&&j<=t)
{
if(j==||S[i]==T[j])
{
++i;
++j;
}
else j=nextval[j];
}
if(j>t)return i-t;
else return ;
}