对于字符串匹配,如用一个长度为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 = %dn",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的位置:%dn",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 %dn",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("%dn",n);
}
}
/*
-1 0 0 1 1 2 3
18 7 7
11
*/