kmp算法

相比于暴力的字串匹配算法，kmp算法在当前不匹配的情况下不会直接退回subStr[0]再重新匹配。

网上盗两张图:

假设i是src串中当前匹配的索引，j是sub串中当前匹配的索引。

则在src[i] != sub[j]时，kmp算法会保持i不变，然后j指向相应的位置。

观察上图可以看出，这个位置应该是sub[0, j - 1](即ABCDAB)中的最长相同前后缀:

即ABCDAB最长前后缀为AB，容易证明只有在这个位置才可以进行最大匹配(前后缀相同)。

具体算法实现如下(next数组就是sub[0, j - 1]的最长前后缀字符数):

 1 int kmpSearch(char* str, char* sub, int next[])
 2 {
 3     int i = 0, j = 0;
 4     int tLen = strlen(str);
 5     int sLen = strlen(sub);
 6     while (i < tLen && j < sLen)
 7     {
 8         // j == -1 第一个不匹配的时候(j = next[0])
 9         // 匹配的时候i、j向后移一位
10         if (j == -1 || str[i] == sub[j])
11         {
12             ++i;
13             ++j;
14         }
15         // 不匹配的时候i不变，j退回next[j]
16         else
17         {
18             j = next[j];
19         }
20     }
21     if (j == sLen)
22         return i - j;
23     return -1;
24 }

View Code

next数组可以递归的求得

 1 void getNext(char* sub, int next[])
 2 {
 3     int len = strlen(sub);
 4     next[0] = -1;
 5     int j = 0, k = -1;
 6     while (j < len - 1)
 7     {
 8         if (k == -1 || sub[j] == sub[k])
 9         {
10             ++k;
11             ++j;
12             next[j] = k;
13         }
14         else
15         {
16             k = next[k];
17         }
18     }
19 }

View Code