1. 定義
- 主串（
S
S
- 模式串（
T
T
- BF算法: BF算法，即暴風(Brute Force)算法，是普通的模式比對算法，BF算法的思想就是将目标串S的第一個字元與模式串T的第一個字元進行比對，若相等，則繼續比較S的第二個字元和 T的第二個字元；若不相等，則比較S的第二個字元和T的第一個字元，依次比較下去，直到得出最後的比對結果。BF算法是一種蠻力算法。 BF算法的時間複雜度O(MN)*。
- KMP算法: KMP算法是一種改進的字元串比對算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，是以人們稱它為克努特—莫裡斯—普拉特操作（簡稱KMP算法）。KMP算法的核心是利用比對失敗後的資訊，盡量減少模式串與主串的比對次數以達到快速比對的目的。具體實作就是通過一個
next()
- 字元串比對算法：用來查找
S
T
BF
KMP
2. BF算法
本算法使用暴力破解的方式進行比對，當模式串
T
從目标串
S
的
i
位開始比對，到
i+n
位失配時，目标串
S
回溯到
i+1
位，模式串
T
回溯到
位
如下圖，主串從第2位比對到第8位時失配
比對位置
i
回溯，主串回溯到(2+1)位，模式串回溯到0位重新開始比對
缺點：相比于KMP算法，BF算法包含了很多不必要的回溯
算法實作
public class BFExample {
public static void main(String[] args) {
String S = "ABCBABCDEF";
String T = "ABCD";
int pos = 0;
BFExample test = new BFExample();
// 遞歸比對
System.out.println(">>>>>>>>>>>>> 遞歸比對T串在S串中的位置");
int begin1 = test.indexOfBFRecursion(S, T, pos);
if (begin1 >= 0) {
// 比對到了
int end1 = begin1 + T.length() - 1;
System.out.println(String.format("%s 位于 %s 的%d-%d位", T, S, begin1, end1));
} else {
// 沒比對到
System.out.println(String.format("%s 不在 %s 中", T, S));
}
// 非遞歸比對
System.out.println(">>>>>>>>>>>>> 非遞歸比對T串在S串中的位置");
int begin2 = test.indexOfBF(S, T, pos);
if (begin2 >= 0) {
// 比對到了
int end2 = begin2 + T.length() - 1;
System.out.println(String.format("%s 位于 %s 的%d-%d位", T, S, begin2, end2));
} else {
// 沒比對到
System.out.println(String.format("%s 不在 %s 中", T, S));
}
}
/**
* 使用遞歸方法，查詢字元串T在S中的起始位置，從pos位置開始
* @param S 主串
* @param T 模式串
* @param pos 起始比對位置
* @return
*/
public int indexOfBFRecursion(String S, String T, int pos) {
// 當起始比對位置+模式串長度大于主串長度，說明模式串在主串中不存在
if (pos + T.length() > S.length()) {
return -1;
}
for (int i = 0; i < T.length(); i++) {
if (S.charAt(pos + i) != T.charAt(i)) {
// 出現不比對的結果，遞歸且起始比對位置pos+1
return indexOfBFRecursion(S, T, ++pos);
}
}
// 比對到了，傳回pos
return pos;
}
/**
* 使用非遞歸方法，查詢字元串T在S中的起始位置，從pos位置開始
* @param S 主串
* @param T 模式串
* @param pos 起始比對位置
* @return
*/
public int indexOfBF(String S, String T, int pos) {
// 當起始比對位置+模式串長度大于主串長度，說明模式串在主串中不存在
if (pos + T.length() > S.length()) {
return -1;
}
// 周遊S串
for (int i = pos; i < S.length(); i++) {
int j;
// 循環比對T串
for (j = 0; j < T.length(); j++) {
if (S.charAt(i + j) != T.charAt(j)) {
break;
}
}
// j == T.length(), 所有字元比對成功，傳回S的索引i
if (j == T.length()) {
return i;
}
}
// 沒比對到
return -1;
}
}
3. KMP算法
KMP算法的基本思路是先将模式串自我比對，得到一個記錄了回溯索引的數組
next
這個數組産生的規則如下
- 字首指的是從0位開始往後的子串
- 字尾指的是從目前位往前的子串
- 使用字首和字尾相等的最大長度作為目前位的回溯索引
- 如ABCABX，目前位為X，字首為AB，字尾為AB時相等且長度最長，那麼X的回溯索引為2
3.1. next
next
假設現在模式串T字首比對到 i 位置，字尾比對到 j 位置
- 如果i = -1，或者目前字元比對成功（即T[i] == T[j]），都令i++，j++，next[j] = i；字尾索引j的後一位對應的回溯索引是字首索引+1（因為i和j都自增了，是以這裡直接使用next[j] = i）
-
如果i != -1，且目前字元比對失敗（即T[i] != T[j]），則令 j 不變，i = next[i]。此舉意味着失配時，字首索引i移動到模式串的next[i]位
算法實作如下：
/**
* 生成next數組
* @param T
* @return
*/
public int[] getNext(String T) {
int len = T.length();
int[] next = new int[len];
int i = -1; // 字首
int j = 0; // 字尾
next[0] = -1; // next[0]既數組第0個元素設定初始值-1，用作回溯判斷
// 周遊T串
while (j < len - 1) {
/**
* -1 == i : 字首沒比對到，從0開始重新比對
* T.charAt(i) == T.charAt(j) : 比對到了
* i和j都往後移一位
*/
if ( (-1 == i) || (T.charAt(i) == T.charAt(j)) ) {
i++;
j++;
next[j] = i;
} else {
// 根據已比對到的next數組回溯i
i = next[i];
}
}
return next;
}
根據以上的規則能生成next數組
3.2. KMP算法比對
上面生成next算法的規則和KMP比對基本類似，
可以了解為回溯的next數組中記錄的回溯的長度就是目标串S與模式串T比對中T向右移可以複用的子串長度
如圖，目标串S在索引8失配，模式串T在索引6失配，此時AB子串可以複用，是以可以将模式串T回溯到2位，再與目标串S的目前位比對
模式串T向右移動6-2位
算法實作
public int indexOfKMP(String S, String T, int pos) {
int[] next = getNext(T);
int i = pos;
int j = 0;
while (i < S.length() && j < T.length()) {
/**
* -1 == j : j沒比對到，從0開始重新比對
* S.charAt(i) == T.charAt(j) : 比對到了
* i和j都往後移一位
*/
if ( (-1 == j) || S.charAt(i) == T.charAt(j)) {
i++;
j++;
} else {
// 根據next數組回溯j的位置
j = next[j];
}
}
// 模式串T比對完成
if (j == T.length()) {
return i - T.length();
}
return -1;
}
3.3. next算法優化
next算法中計算了最長的字首和字尾，但是在一下場景中存在優化點
當模式串T的第3位A失配時，按照前面的邏輯是回溯到第2位的A，但是由于A在目标串S的第3位失配，是以這裡的回溯是多餘的操作
優化後的next在比對到i和j位的字元相同時，直接在j位複用i位的索引，得到如下的next結構
代碼實作：
/**
* 生成next數組
* @param T
* @return
*/
public int[] getNext(String T) {
int len = T.length();
int[] next = new int[len];
int i = -1; // 字首
int j = 0; // 字尾
next[0] = -1; // next[0]既數組第0個元素設定初始值-1，用作回溯判斷
// 周遊T串
while (j < len - 1) {
/**
* -1 == i : 字首沒比對到，從0開始重新比對
* T.charAt(i) == T.charAt(j) : 比對到了
* i和j都往後移一位
*/
if ( (-1 == i) || (T.charAt(i) == T.charAt(j)) ) {
i++;
j++;
/**
* 當字首相等時，如果失配可以直接回溯到第一個之前的位置
* 如：T = XAAAAAX
* 當在T[5]處失配時，則證明T[1-4]也會失配，是以直接回溯到T[1]的值所指向的索引0
*/
// next[j] = i;
/******** 改進 ********/
if (T.charAt(i) != T.charAt(j)) {
next[j] = i;
} else {
next[j] = next[i];
}
/******** 改進 ********/
} else {
// 根據已比對到的next數組回溯i
i = next[i];
}
}
return next;
}
END
以上算法就是KMP算法的大緻講解