对于字符串匹配，如用一个长度为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-
,
