KMP

 1 #include <stdio.h>
 2 
 3 typedef char* String;
 4 
 5 void getnext(String T, int *next)
 6 {
 7     j=0, i=1;
 8     next[1] = 0;
 9     while ( i < T[0])
10     {
11         if ( j==0||T[i]==T[j])
12         {
13             i++;
14             j++;
15             if ( T[i] != T[j])
16             {
17                 next[i] = j;
18             }
19             else                    //改进后
20             {
21                 next[i] = next[j];
22             }
23         }
24         else
25         {
26             //j回溯
27             j = next[j];
28         }
29     }
30 }
31 
32 //返回子串T在主串S第pos个字符之后的位置
33 // 若不存在，则返回0
34 int Index_KMP(String S, String T, int pos)
35 {
36     int i = pos;
37     int j = 1;
38     int next[255];
39     
40     getnext (T, next);
41     
42     while (i <= S[0] && j<=T[0] )
43     {
44         if (S[i] == T[j] || j==0)
45         {
46             i++;
47             j++;
48         }
49         else
50         {
51             j = next[j];
52         }
53     }
54     
55     if (j > T[0])
56     {
57         return i - T[0];
58     }
59     else
60     {
61         return 0;
62     }
63 }