kmp算法与特点（经典算法kmp大神级的存在）

对于字符串匹配，如用一个长度为m的模式串去匹配一个长度为n的主串，我们可以使用暴力法（BF，Brute Force），其时间复杂度为O(m*n)。

字符串匹配kmp算法的时间复杂度只需要O(m n)。

使用变量 i, j 表示主串s[]和模式串t[]的下标， 第一轮匹配：

kmp算法认为，i 可以不回退（BF要求退回到主串的第2个位置（第几轮就是第几个位置）），而 j 可以回退到第2个位置，即 j=2（BF要求退回到每1个字符的位置）。

即使使用暴力破解，几轮迭代后，也会迭代匹配到此位置，所以上述 i，j 的回退不影响整体结果的正确性。

模式串此时回退为什么是2呢？

看下面已匹配的公共部分：

主串以不匹配的位置为基准，考虑前面的字符abaab，有后缀ab与模式串abaabe最前面的字符前缀ab相等。

也就是模式串本身abaab，有最大后缀部分ab与最大前缀ab相等，相等字符的长度为2。

从上图可见，假设一个字符串长度为n，其最大前缀和后缀相等的字符数量不会超过n/2，例如：

abcdabcd，长度为8，8/2=4，其最大前缀和后缀相等的字符串abcd最大可能的长度为4。

如何暴力计算下面字符的最大前缀和后缀字符串的长度L呢？

abcdaabbcdeabcd，长度n为15，其L不会超过n/2=7，暴力匹配的思路可以描述为：

前1个字符与后1个字符是否相等？

前2个字符与后2个字符是否相等？

前3个字符与后3个字符是否相等？

……

前n/2个字符与后n/2个字符是否相等？

暴力匹配的思路也可以描述为：

前n/2=7个字符与后n/2=7个字符是否相等？

abcdaabbcdeabcd

前n/2-1=6个字符与后n/2-1=6个字符是否相等？

abcdaabbcdeabcd

前n/2-2=5个字符与后n/2-2=5个字符是否相等？

abcdaabbcdeabcd

abcdaabbcdeabcd

前n/2-3=4个字符与后n/2-3=4个字符是否相等？

abcdaabbcdeabcd

此时相等，则L为4。

对于模式串abaabe，如何计算各个子串对应的最大前缀与后缀字符串数量（j回退到的位置）？

abaab	2
abaa	1
aba	1
ab	0
a	-1

图示：

对应代码：

int *getNextArray(char t[]) // 动态规划 { int n = strlen(t); int *next = (int*)malloc(sizeof(int)*n); next[0] = -1; next[1] = 0; int k; for (int j = 2; j < n; j ) { k=next[j-1]; // 先假设 while (k!=-1) { if (t[j - 1] == t[k]) { next[j] = k 1; break; }else k = next[k]; // 回退 next[j] = 0; //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值 } } return next; }

对于模式串T的下标 j 回退位置next[]的求解方法，KMP算法应用的动态规划的思想：

首先大胆假设next[j]=k，则

那么next[j 1]=?

也就是以上子串再分别多考虑一个随后的字符：

可以区分这两个字符在相等和不等的情况下分别考虑：

有了确定模式串回退位置的数组，字符串匹配剩下的代码就相对较容易了。

demo c code：

#include <stdio.h> #include <malloc.h> #include <string.h> // 对主串s和模式串t进行KMP模式匹配 // 计算模式串t需要回退的位置（BF是回退到0） int *getNextArray(char t[]) // 动态规划 { int n = strlen(t); int *next = (int*)malloc(sizeof(int)*n); next[0] = -1; next[1] = 0; int k; for (int j = 2; j < n; j ) { k=next[j-1]; // 先假设 while (k!=-1) { if (t[j - 1] == t[k]) { next[j] = k 1; break; }else k = next[k]; // 回退 next[j] = 0; //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值 } } return next; } /** * 对主串s和模式串t进行KMP模式匹配 * @param s 主串 * @param t 模式串 * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1 */ int kmpMatch(char* s, char* t){ int *next = getNextArray(t); int i = 0, j = 0; while (i<(int)strlen(s) && j<(int)strlen(t)){ if(j == -1 || s[i]==t[j]){ i ; j ; } else j = next[j]; } //printf("\ni-j = %d - %d = %d\n",i,j,i-j); if(j == (int)strlen(t)) return i-j; else return -1; } int main() { //char* str[] = {"ACBACAACAACACAACAB","ACAACAB"}; //char* str[] = {"abaabaabeca","abaabe"}; char* str[] = {"abaabaeabaabea","abaabe"}; int *next = getNextArray(str[1]); int i,j; printf("主串s[]= "); for(i=0;i<(int)strlen(str[0]);i ) printf("%c ",str[0][i]); printf("\n"); for(i=0;i<2;i ) { printf("模式串t[]= "); for(j=0;j<(int)strlen(str[1]);j ) printf("%c ",str[1][j]); printf("\n"); } printf("next[] = "); for(i=0;i<strlen(str[1]);i ) printf("%d ",next[i]); int n = kmpMatch(str[0],str[1]); printf("\n模式串t首次匹配到主串s的位置：%d\n",n); getchar(); } /* 主串s[]= a b a a b a a b e c a 模式串t[]= a b a a b e 模式串t[]= a b a a b e next[] = -1 0 0 1 1 2 模式串t首次匹配到主串s的位置：3 主串s[]= A C B A C A A C A A C A C A A C A B 模式串t[]= A C A A C A B 模式串t[]= A C A A C A B next[] = -1 0 0 1 1 2 3 模式串t首次匹配到主串s的位置：11 主串s[]= a b a a b a e a b a a b e a 模式串t[]= a b a a b e 模式串t[]= a b a a b e next[] = -1 0 0 1 1 2 模式串t首次匹配到主串s的位置：7 */

demo java code：

class Ideone { public static int[] getNextArray(char[] t) { int[] next = new int[t.length]; next[0] = -1; next[1] = 0; int k; for(int j = 2; j < t.length; j ) { k=next[j-1]; while(k!=-1) { if(t[j - 1] == t[k]) { next[j] = k 1; break; } else { k = next[k]; } next[j] = 0; //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值 } } return next; } /** * 对主串s和模式串t进行KMP模式匹配 * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1 */ public static int kmpMatch(String s_arr, String t_arr){ char[] s = s_arr.toCharArray(); char[] t = t_arr.toCharArray(); int[] next = getNextArray(t); for(int i=0;i<t.length;i ) System.out.print(next[i] " "); int i = 0, j = 0; while(i<s.length && j<t.length){ if(j == -1 || s[i]==t[j]){ i ; j ; } else j = next[j]; } System.out.printf("\n%d %d %d\n",i,j,t.length); if(j == t.length) return i-j; else return -1; } public static void main (String[] args) throws java.lang.Exception { int n = kmpMatch("ACBACAACAACACAACAB","ACAACAB"); System.out.printf("%d\n",n); } } /* -1 0 0 1 1 2 3 18 7 7 11 */

-End-

,