数据结构——

数据结构———KMP

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

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

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int nextv[10000],len_s,len_t;
 7 char s[10000],t[10000];
 8 void get_nextv()
 9 {
10     int i=0,j=-1;
11     nextv[0]=-1;
12     while(i<len_t)
13     {
14         if(j==-1||t[i]==t[j])
15         {
16             ++i; ++j;
17             if(t[i]!=t[j]) nextv[i]=j;
18             else nextv[i]=nextv[j];
19         }
20         else
21         j=nextv[j];
22     }
23 }
24 
25 int kmp()
26 {
27     int i=0,j=0;
28     while(i<len_s&&j<len_t)
29     {
30         if(j==-1||s[i]==t[j])
31         {
32             ++i; ++j;
33         }
34         else  j=nextv[j];
35     }
36     if(j>=len_t)  return 1;
37     else return -1;
38 }
39 int main()
40 {
41     while(scanf("%s%s",s,t)!=EOF)
42     {
43         len_s=strlen(s); len_t=strlen(t);
44         get_nextv();
45         if(kmp()!=-1)
46         cout<<"YES"<<endl;
47         else
48         cout<<"NO"<<endl;
49     }
50     return 0;
51 }