sdut 2125串结构练习--字符串匹配【两种KMP算法】

串结构练习——字符串匹配

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 ;
 }