KMP示例程序

输入：

　　数字N，然后是N组数据，每一组数据第一行是模式串p，第二行是一个大的字符创s，如果在s里面出现了p，那么输出p第一次出现的位置，否则输出No

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 char p[1000], s[1000];
 7 int next[1000];
 8 void getnext() {
 9   int i = 0, j = -1, len = strlen(p);
10   next[0] = -1;
11   while (i < len - 1) {
12     if (j == -1 || p[j] == p[i]) {
13       j++; i++; next[i] = j;
14     }
15     else j = next[j];
16   }
17 }
18 int kmp() {
19   int i = -1, j = -1, lenp = strlen(p), lens = strlen(s);
20   getnext();
21   while (j != lenp && i < lens) {
22     if (j == -1 || s[i] == p[j]) {++i; ++j;}
23     else j = next[j];
24   }
25   if (j == lenp) return i - j;
26   else return -1;
27 }
28 int main(void) {
29 #ifndef ONLINE_JUDGE
30   freopen("kmp.in", "r", stdin);
31 #endif
32   int n;
33   while (~scanf("%d", &n)) 
34   while (n--){
35     scanf("%s%s", p, s);
36     if (kmp() == -1) {
37       printf("No\n");
38     } else printf("%d\n", kmp());
39   }
40 
41   return 0;
42 }

KMP好神奇，不愧是高老大！