数据结构———KMP

今天照着课本敲了一下KMP..

以OJ上的一个题为例敲了一下。。

题目：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2125

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int nextv[],len_s,len_t;

 char s[],t[];

 void get_nextv()

 {

     int i=,j=-;

     nextv[]=-;

     while(i<len_t)

     {

         if(j==-||t[i]==t[j])

         {

             ++i; ++j;

             if(t[i]!=t[j]) nextv[i]=j;

             else nextv[i]=nextv[j];

         }

         else

         j=nextv[j];

     }

 }

 int kmp()

 {

     int i=,j=;

     while(i<len_s&&j<len_t)

     {

         if(j==-||s[i]==t[j])

         {

             ++i; ++j;

         }

         else  j=nextv[j];

     }

     if(j>=len_t)  return ;

     else return -;

 }

 int main()

 {

     while(scanf("%s%s",s,t)!=EOF)

     {

         len_s=strlen(s); len_t=strlen(t);

         get_nextv();

         if(kmp()!=-)

         cout<<"YES"<<endl;

         else

         cout<<"NO"<<endl;

     }

     return ;

 }