KMP匹配：時間復雜度O(m + n)
/**
* @param originS 長字符串
* @param matchedS 要匹配的字符串
* @return 匹配字符在長字符串中的位置
*/
private static int kmpMatch(String originS, String matchedS) {
// next 數組各值的含義：代表當前字符之前的字符串中，有多大長度的相同前綴后綴。
// 例如如果next [j] = k，代表j 之前的字符串中有最大長度為k 的相同前綴后綴
char[] originArray = originS.toCharArray();
char[] matchedArray = matchedS.toCharArray();
int originLen = originS.length();
int matchedLen = matchedS.length();
int[] next = getNext(matchedArray);
int i = 0, j = 0;
while (i < originLen && j < matchedLen) {
if (j == -1 || originArray[i] == matchedArray[j]) {
// 相等則繼續位移比較(需要同時移位)
i++;
j++;
} else {
// j != -1，且當前字符匹配失敗（originArray[i] != matchedArray[j]），則令 i 不變，j = next[j]
// next[j]即為j所對應的next值
// 失配時，模式串向右移動的位數為：已匹配字符數 - 失配字符的上一位字符所對應的最大長度值
// 失配時，模式串向右移動的位數為：失配字符所在位置 - 失配字符對應的next 值
j = next[j];
}
}
// 匹配字符串完全找到
if (j == matchedLen) {
return i - j;
} else {
return -1;
}
}
/**
* 獲取失配時的位移數組
* 求解原理為:
* 1. 匹配字符串的前綴后綴的公共元素的最大長度值的對應數組
* 2. eg: abab : 0 0 1 2
* 3. 最大對稱長度的前綴后綴，然后整體右移一位，初值賦為-1
* 4. eg: abab : -1 0 0 1
* @param matchedArray 需要匹配的pattern字符串
* @return 位移數組
*/
private static int[] getNext(char[] matchedArray) {
int matchedLen = matchedArray.length;
int[] next = new int[matchedLen];
next[0] = -1;
int k = -1;
int j = 0;
while (j < matchedLen - 1) {
// matchedArray[k]表示前綴，matchedArray[j]表示后綴
// matchedArray[j] == matchedArray[k] 此判斷是因為matchedArray[j]已經失配,用相同的matchedArray[k], 位移后去匹配一樣是失配.
// 故二者相等時,繼續遞歸
if (k == -1 || matchedArray[j] == matchedArray[k]) {
++k;
++j;
next[j] = k;
} else {
k = next[k];
}
}
return next;
}
