字符串匹配 KMP 算法
KMP算法是 BF(Brute Force) 算法的一种改进算法,是一种较为高效的字符串匹配算法。
相比 BF 暴力匹配算法,KMP 算法的思想是利用已匹配的信息,使得能够不发生回溯,也就是当发生不匹配时,文本串(source)的位置不变,尽量向右移动模式串(target),如下图所示:
前缀与后缀
KMP 算法的核心是 next 数组的求解,而要理解 next 数组需要先理解前缀和后缀的概念。
事实上,对于不含有重复字符的模式串,比如“ABCD”,并不需要前缀和后缀,当下标为i处不匹配时,只需将模式串向右移动i位继续进行匹配即可(下标从0开始)。如下图所示:
为了避免这种情况发生,引入前缀、后缀概念。
以字符串“abcdabd”为例,
- 前缀:a,ab,abc,abcd,abcda,abcdab
- 后缀:d,bd,abd,dabd,cdabd,bcdabd
失配时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值,如果是首位发生失配,即向右移动一位。
代码求解 next 数组是利用已知的 next[i] 求解 next[i+1],如下图所示:
KMP算法的Java实现
public class KMP {
private static int[] next;
//next数组求解
public static int[] getNext(String str) {
char[] source = str.toCharArray();
int length = source.length;
next = new int[length];
next[0] = -1;
int k = -1;
int j = 0;
while (j < length - 1) {
if (k == -1 || source[j] == source[k]) {
j++;
k++;
if (source[j] != source[k])
next[j] = k;
else
next[j] = next[k];
} else {
k = next[k];
}
}
return next;
}
public static int kmpSearch(String str, String target) {
int i = 0, j = 0;
char[] source = str.toCharArray();
char[] pattern = target.toCharArray();
int sLen = source.length;
int pLen = pattern.length;
while (i < sLen && j < pLen) {
//如果j = -1,或者当前字符匹配成功
if (j == -1 || source[i] == pattern[j]) {
i++;
j++;
} else {
//如果j != -1,且当前字符匹配失败
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
public static void main(String[] args) {
String source = "abacababc";
String target = "cab";
getNext(target);
int position = kmpSearch(source, target);
if (position != -1)
System.out.print("成功匹配,起始位置是:" + position);
else {
System.out.println("未成功匹配!");
}
}
}
运行结果:
成功匹配,起始位置是:3
参考文章: