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

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

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

kmp算法与特点(经典算法kmp大神级的存在)(1)

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

kmp算法与特点(经典算法kmp大神级的存在)(2)

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

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

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

kmp算法与特点(经典算法kmp大神级的存在)(3)

主串以不匹配的位置为基准,考虑前面的字符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

图示:

kmp算法与特点(经典算法kmp大神级的存在)(4)

对应代码:

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,则

kmp算法与特点(经典算法kmp大神级的存在)(5)

那么next[j 1]=?

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

kmp算法与特点(经典算法kmp大神级的存在)(6)

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

kmp算法与特点(经典算法kmp大神级的存在)(7)

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

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-

,