KMP (?_?)
今天做LC214. Shorest Palindrome, 第一次接触KMP算法。借此机会学习一下KMP算法。👇 然后发现不用KMP也能做
KMP算法是两个字符串匹配的算法，例如，在S(S.length = n)串中寻找P(P.length = m)串是否存在。暴力的方法就是以S的每一位字符为起始开始匹配P，如果没有匹配成功就后移一位直到匹配结束。这样的话复杂度为O(n*m)。总觉得不太妙啊…KMP算法能够通过对P进行预处理使算法复杂度降为O(n + m) 好厉害❤
The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of the next window. We take advantage of this information to avoid matching the characters that we know will anyway match.
举个例子假设S = “ATOBXATOBEKEIGO❤”, P = “ATOBE” , 从i = 0开始匹配，到i = 4时失配，那么感觉上应该是从 i = 4开始匹配 j = 0， 如果S = ‘ATATXBEATOBEKEIGO❤’ ，P = ‘ATATOBE’, 在i = 4失配，感觉上就应该从 i = 4开始匹配 j = 2才对。这种感觉是怎么来的呢？原来是因为P字符串中自身的重复性导致的。所以针对P的自身结构进行预处理得到模式值数组(prefix function)，再根据每次失配的位置对应此数组内的值就可以得到下一个开始进行匹配的位置(i, j)了。
模式值数组(Prefix Function)的求取
一般这个模式值数组定义为next，其长度与模式P串相同。next数组有不同的表示方法，我就偷懒理解一种会用就行啦。
next[j] = -1: 在index = j前面并没有和自身重复的子序列出现
next[j] = k (0 <= k < P.length): 存在[0 - k]区域的P子序列，其末位在P中为j(j != k)
举几个🌰：
P = "ATATOBE" -> P.next = [-1, -1, 0, 1, -1, -1, -1]
P = "ATOBEAT" -> P.next = [-1, -1, -1, -1, -1, 0, 1]
P = "YYAOYYY" -> P.next = [-1, 0, -1, -1, 0, 1, 1]
代码实现：
public int[] getNext(String P){
int n = P.length();
char[] Parr = P.toCharArray();
int[] next = new int[n];
Arrays.fill(next, -1);
int i = 0, j = 1; // 从第二位开始
for(; j < n; j++){
i = next[j-1]; // 从上一位继承
while(Parr[i+1] != Parr[j] && i >= 0) i = next[i]; // 非连续的匹配位置, 例如上面的例3
if(Parr[i+1] == Parr[j]) next[j] = i + 1; // 匹配则后移一位
else next[j] = -1; // 不匹配
}
return next;
}
匹配
看起来不错，求得了next之后就可以匹配了，当发现P[j + 1]位不匹配，只要回溯到P[next[j]+1]位开始匹配。例如S = “ATATXBEATOBEKEIGO❤”， P = “ATATOBE”， 在 i = 4失配，这里next = [-1, -1, 0, 1, -1, -1, -1]， 因此在从 i = 4开始对 j = 2开始匹配。
代码实现：
public List<Integer> kmp(String S, String P){
int[] next = getNext(P);
int s = S.length(), p = P.length();
int i = 0, j = -1;
char[] sarr = S.toCharArray();
char[] parr = P.toCharArray();
List<Integer> match = new ArrayList<Integer>();
for(i = 0; i < s; i++){
// not match, go to next[j]
while(parr[j + 1] != sarr[i] && j >= 0) j = next[j];
// match, go to next char
if(parr[j + 1] == sarr[i]) j++;
// match, add to result and go to next
if(j == p - 1){
match.add(i - j);
j = next[j];
}
} // for
return match;
}
算法复杂度
装模作样的分析一番复杂度。getNext的复杂度是O(P.length), 对于for循环，其中的while循环最多回溯j步。在整个对于i的for循环中，i的最大增量为S.length，所以while最多执行S.length次。for循环的复杂度为S.length. 总而言之O(len1 + len2)，比O(len1 * len2)感觉好多啦。