KMP算法又称模式串匹配:给定字符串partten,要求在字符串text中找到partten第一次出现的坐标并返回。
暴力匹配:public int strStr(String text, String partten) {
if (text.contains(partten)) {
int n = partten.length();
for (int i = 0; i < text.length(); i++) {
if(text.substring(i, i+n) == partten){
return i;
}
}
}
return -1;
}
时间复杂度是O(mn)
KMP比暴力匹配就在于,如果遇到不适配的字符,KMP知道退到哪里,而不是将partten已经适配的字符完全丢掉。具体过程如下:
我们知道KMP知道退回哪个位置的重点在于它记录了一个next数组,这个next数组具体怎么算的呢?
模式串pattern:ABABCABAA,要求next数组,必须先求pattern最长公共前缀后缀数组prefix:
| partten | A | B | A | B | C | A | B | A | A |
| prefix | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 1 |
A:0
AB:0
ABA:1
ABAB:2
ABABC:0
ABABCA:1
ABABCAB:2
ABABCABA:3
ABABCABAA:1
怎么用代码来实现这个prefix数组的求解呢??
i为pattern的索引,len是最长公共前后缀长度。初始i=1;len=0;
我们需要不断判断 pattern[i] 和 pattern[len] 是否相等
等的情况:
让len直接+1
不等的情况:因为当前i和len对应的字符不一样了,所以我们直接就让len等于它前一个prefix对应的长度了。
最终代码实现得到最长公共前后缀数组:
// 根据模式串求出最长公共前后缀数组
public int[] getPrefix(String needle) {
int[] prefix = new int[needle.length()];
prefix[0] = 0;
int i = 1;
int len = 0;
while (i < needle.length()) {
if (needle.charAt(i) == needle.charAt(len)) {
len++;
prefix[i] = len;
i++;
} else{
if (len > 0) { // 只要当len大于0,减一,prefix下标才不会越界
len = prefix[len - 1];
prefix[i] = len;
}else{ // 否则直接不处理
prefix[i] = len;
i++;
}
}
}
return prefix;
}
如何根据prefix表得到next数组呢?prefix整体向后移动一位,第一个元素置为-1,最后一个prefix元素舍弃;
代码得到next数组:
// 根据最长公共前后缀得到模式串的next数组
public int[] getNext(int[] prefix) {
int[] next = new int[prefix.length];
next[0] = -1;
for (int i = 1; i < prefix.length; i++) {
next[i] = prefix[i - 1];
}
return next;
}
根据next数组进行模式匹配了:
i指向text,j指向pattern,
如果对应字符适配,则:i++,j++;
如果不适配,则j = next[j],如果j==-1,则j++,i++;
代码实现:
public int search(String haystack, String needle) {
int[] prefix = getPrefix(needle);
int[] next = getNext(prefix);
int i = 0;
int j = 0;
while (i < haystack.length() && j < needle.length()) {
if (haystack.charAt(i) == needle.charAt(j)) { // 适配,i和j同时前移
i++;
j++;
} else { // 不适配,j后退
j = next[j];
if (j == -1) { // 如果j后退到-1,说明j处于pattern的其实位置,那么i和j就同时前移
j++;
i++;
}
}
}
if (j == needle.length()) {
return i - needle.length();
}
return -1;
}
结束。



