最近 Android 做了一個全文關(guān)鍵字高亮的功能，直接用了
Java 現(xiàn)成的 API 解決了，在查閱資料的過程中得知還有幾種匹配算法：BF、RK、KMP、BM、Sunday，有空就做了一些了解。這里記錄一下防止忘記，阮一峰大神關(guān)于這些算法的博客寫的很好。
BF
暴力檢索，這種方法最容易想到，也是最容易實現(xiàn)的，從首字母開始挨個的將關(guān)鍵字和做比對。用下面的圖片就能只管的說明（圖片來自阮一峰大神的博客）
代碼實現(xiàn)：
package other.string.textmatch;
/**
* 暴力檢索
*/
public class BFMatch {
/**
* 暴力檢索，輸出匹配到的關(guān)鍵字的起始索引（包括起始索引在內(nèi)，因為有的是不包括結(jié)尾下標(biāo)在內(nèi)，所以這里說明一下）
*
* @param originText 原始文字
* @param keyword 要匹配的關(guān)鍵字
*/
public static void BFMatch(String originText, String keyword) {
char originChar;
for (int i = 0; i < originText.length(); i++) {
for (int j = 0; j < keyword.length(); j++) {
if (i + j >= originText.length()) break;
originChar = originText.charAt(i + j);
if (originChar != keyword.charAt(j)) {
break;
}
if (j == keyword.length() - 1) {
System.out.println("找到匹配字符串，起始：" + i +
" 終止：" + (i + keyword.length() - 1));
}
}
}
}
public static void main(String... args) {
BFMatch("asdfj9iwhefpnehbnfhodhsvb", "j9");
}
}
輸出：
找到匹配字符串，起始：4 終止：5
RK
RK 算法是對 BF 算法的一個改進(jìn)，看了我上面對 BF 的實現(xiàn)不難發(fā)現(xiàn)，每次匹配都需要比對每一個字符是否一致，是否有更加有效率的方法呢？有的，RK 對于 BF 的改進(jìn)就在于嘗試進(jìn)行一次比較來判斷兩者是否相等。RK 算法首先計算子串的哈希值，然后在原字符串中取出同樣長度的字符串計算哈希值，如果二者的哈希值不等那么他們一定不同。如果哈希值相同，由于哈希沖突的存在，也需要再次比對一下是否相同。一般情況下我們需要匹配的文本含有的關(guān)鍵字占全文的數(shù)量應(yīng)該不是很高，所以這種高效率去除不同的情況效率是高于 BF 的?？匆幌聦崿F(xiàn)：
package other.string.textmatch;
public class RKMatch {
/**
* 暴力檢索的改進(jìn)，輸出匹配到的關(guān)鍵字的起始索引（包括起始索引在內(nèi)，因為有的是不包括結(jié)尾下標(biāo)在內(nèi)，所以這里說明一下）
*
* @param originText 原始文字
* @param keyword 要匹配的關(guān)鍵字
*/
public static void RKMatch(String originText, String keyword) {
int keyHash = keyword.hashCode();
int keyLength = keyword.length();
String subString;
for (int i = 0; i < originText.length(); i++) {
if (keyLength + i >= originText.length()) break;
subString = originText.substring(i, i + keyLength);
if (subString.hashCode() == keyHash) {
for (int j = 0; j < keyLength; j++) {
if (subString.charAt(j) != keyword.charAt(j)) break;
if (j == keyLength - 1) {
System.out.println("找到匹配字符串，起始：" + i +
" 終止：" + (i + keyword.length() - 1));
}
}
}
}
}
public static void main(String... args) {
RKMatch("asdfj9iwhefpnehbnfhodhsvb", "j9");
}
}
輸出：
找到匹配字符串，起始：4 終止：5
KMP
哇，真是大學(xué)時的噩夢?。ㄐΓ?，字符串匹配的最經(jīng)典算法之一，曾被票選為當(dāng)今世界最偉大的十大算法之一。恩，先回到正題吧，不閑扯了，KMP 算法我看了一下，覺得比較難的部分就是部分匹配值的計算了。BF 和 RK 在匹配不上時都是順序向后移動一位繼續(xù)匹配，而 KMP 不是，是按照計算的部分匹配值來向后移動。這里不具體解釋原理，直說按照怎樣的步驟去實現(xiàn)計算部分匹配值：
“部分匹配值”是指字符串前綴和后綴所共有元素的長度。前綴是指除最后一個字符外，一個字符串全部頭部組合；后綴是指除第一個字符外，一個字符串全部尾部組合。以”ABCDABD”為例：
“AB”的前綴為[A]，后綴為[B]，共有元素的長度為0；
“ABC”的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度0；
“ABCD”的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為0；
“ABCDA”的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為”A”，長度為1；
“ABCDAB”的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為”AB”，長度為2；
“ABCDABD”的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0。
代碼實現(xiàn)：
/**
* 計算部分匹配值
*/
public static int[] calcPartMatch(String keyword) {
int[] partMatchVal = new int[keyword.length()];
for (int i = 0; i < keyword.length(); i++) {
if (i == 0) {
partMatchVal[0] = 0;
continue;
}
String subKey = keyword.substring(0, i + 1);
// 求前綴
list1.clear();
for (int j = 1; j < subKey.length(); j++) {
list1.add(subKey.substring(0, j));
}
// 求后綴
list2.clear();
for (int j = 1; j < subKey.length(); j++) {
list2.add(subKey.substring(j, subKey.length()));
}
System.out.println("\ni = " + i);
for (String s : list1) {
System.out.println("前綴：" + s);
}
for (String s : list2) {
System.out.println("后綴：" + s);
}
// 求交集
list1.retainAll(list2);
int length = 0;
for (String str : list1) {
if (str.length() > length) length = str.length();
}
// if (list1.size() == 0) partMatchVal[i] = 0;
// else {
// partMatchVal[i] = list1.size();
// }
partMatchVal[i] = length;
System.out.println("\n長度為：" + partMatchVal[i]);
}
return partMatchVal;
}
輸入 ada ，輸出：
i = 1
前綴：a
后綴：d
長度為：0
i = 2
前綴：a
前綴：ad
后綴：da
后綴：a
長度為：1
計算得出的部分匹配值就是0、0、1
KMP算法實現(xiàn)：
/**
* 流程比較復(fù)雜，注釋里比較難寫清，具體可見
* http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
* <p>
* 具體的操作流程就是：
* 1.計算 keyword 的部分匹配值
* 2.進(jìn)行匹配操作，碰到部分匹配成功，下一次 起始點索引 = 原位置 + 已匹配的字符數(shù) - 對應(yīng)的部分匹配值
*/
public static void kmpMatch(String originText, String keyword) {
// 部分匹配值
int[] partMatch = calcPartMatch(keyword);
for (int i = 0; i < originText.length(); ) {
char c;
// 匹配字符數(shù)
int count = 0;
for (int j = 0; j < keyword.length(); j++) {
if (i + j >= originText.length()) break;
c = originText.charAt(i + j);
if (c != keyword.charAt(j)) {
break;
}
count++;
if (j == keyword.length() - 1) {
System.out.println("找到匹配字符串，起始：" + i +
" 終止：" + (i + keyword.length() - 1));
}
}
if (count == 0) {
i++;
} else {
i += count - partMatch[count - 1];
}
if (i > originText.length()) break;
}
}
輸入：kmpMatch("asdfasdfasdfasdfadae4rqerfasdfv", "ada");
輸出：找到匹配字符串，起始：16 終止：18
這里還有 BM 和 Sunday 沒有實現(xiàn)。
