KMP算法
kmp是字符串匹配算法。
主要用途：搜索匹配字符串中的子串p的位置
原理
1 字符串的前缀和后缀
| 串 | 前缀 | 后缀 | 最长公共串 | 最长公共长度 |
| a | - | - | 无 | 0 |
| ab | a | b | 无 | 0 |
| abc | a,ab | c,bc | 无 | 0 |
| abca | a ,ab,abc | a ,ca,bca | a | 1 |
| abcab | a, ab,abc,abca | b, ab ,cab,bcab | ab | 2 |
| abcabc | a,ab, abc,abca,abcab | c,bc, abc,cabc,bcabc | abc | 3 |
2 搜索匹配值表
| 搜索词 | a b c a b c |
| 匹配值 | 0 0 0 1 2 3 |
表是从上面的前缀后缀计算出来的
3 kmp算法流程 a:先求公共最大长度 b:计算出对比数组next
4 例子：
在字符串 BBC ABCDAB ABCDABCDABDE
搜索 ABCDABD
过程：
1 求部分匹配值表
| 串 | 前缀 | 后缀 | 最长公共串 | 最长公共长度 |
| A | - | - | 无 | 0 |
| AB | A | B | 无 | 0 |
| ABC | A,AB | C,BC | 无 | 0 |
| ABCD | A,AB,ABC | D,CD,BCD | 无 | 0 |
| ABCDA | A,AB,ABC,ABCD | A,DA,CDA,BCDA | A | 1 |
| ABCDAB | A, AB ,ABC,ABCD,ABCDA | B, AB,DAB,CDAB,BCDAB | AB | 2 |
| ABCDABD | A,AB ,ABC,ABCD,ABCDA,ABCDAB | D,BD,ABD,DABD,CDABD,BCDABD | 无 | 0 |
2 部分匹配值表
| 搜索词 | A B C D A B D |
| 匹配值 | 0 0 0 0 1 2 0 |
3 匹配过程第一步
已知空格与D不匹配时，前面6个字符’ABCDAB’是匹配的。查搜索子串匹配表可知匹配字符B对应的 部分匹配值为2 ，因此按照下面的公式算出向后移动的位数：
移动位数 = 已匹配字符数 - 对应部分匹配值
4 = 6 -2
所以向后移动4位，继续往后移动
匹配过程第二步
因为空格与C不匹配，搜索词继续往后移动；已匹配字符为‘AB’个数为2；C对应部分匹配值为0;则移动2-0 = 2位；
以次匹配直至找到为止
代码实现：
//pattern //abcabc //k=0 //q=1 void make_next(const char *pattern, int *next){ int q, k; int m = strlen(pattern); next[0] = 0; //第一位默认0 for(q = 1, k=0; q < m; q++){ while( k > 0 &&pattern[q] != pattern[k]) { k = next[k-1]; } if (pattern[q] == pattern[k]) { //前缀和后缀有相同的字符 k++; } next[q] = k; } } int kmp(const char *text, const char *pattern, int *next) { int n = strlen(text); int m = strlen(pattern); make_next(pattern, next); int i, q; for(i = 0, q = 0; i<n;i++){ while(q>0 &&pattern[q] != text[i]){ q = next[q-1]; } if (pattern[q] == text[i]){ q++; } if (q == m){ break; } } return i-q+1; }
测试代码：
int main() { char *text = "abcabcabcabcabcd"; char *pattern = "abcabcd"; int next[20] = {0}; int idx = kmp(text, pattern, next); printf("match pattern: %d\n", idx); return 0; }
结果：
完整代码：
