号沒留言功能，是以我建了個微信交流群來友善交流，現在需要你的加入，群裡大佬賊多！目前入群滿百發紅包，給個一起吹比的機會把阿Sir，期待與你一起互相吹捧，共同進步。對了，以後文章定時18:20見。
1 暴力破解法
在主串A中查找模式串B的出現位置，其中如果A的長度是n，B的長度是m，則n > m。當我們暴力比對時，在主串A中比對起始位置分别是 0、1、2….n-m 且長度為 m 的 n-m+1 個子串。
暴力比對
對應代碼是：
#include<stdio.h>
#include<string.h>
int cnt=0;
int index(char s[], char sub[])
{
int i=0;
int j=0;
while(i<strlen(s))
{
if(s[i]==sub[j])
{ //單個字元相等的話 i和j都向後搜尋
i++;
j++;
}
else
{ //有字元不比對的話,i從上一次的下一個位置開始,模式串j再從0開始
i=i-j+1;
j=0;
}
if(j==strlen(sub))
{
cnt++;
return i-strlen(sub)+1;
}
}
return -1;
}
int main()
{
// s="abcdabefgabefa"，sub="abe"，傳回 5。
char s[20],sub[10];
gets(s);
gets(sub);
printf("%d\n",cnt);
printf("%d\n",index(s,sub));
return 0;
}
如果主串是bbb…bbb，模式串是bbbbc，那每個串都要比較m次，一共是(n-m+1)*m次。時間複雜度很大 =
O(n*m)
，一般簡單比對時候可用此法。
2 Rabin-Karp 算法
算法思路
：對主串的 n-m+1 個子串分别求哈希值，然後跟模闆串的哈希值對比，如果一樣再逐個對比字元串是否一樣。
Rabin-Karp算法
但是中間資料的Hash值計算是可以優化的，我們以簡單的字元串比對舉例，把a-z映射到0~25上。然後按照26進制計算一個串的哈希值，比如：
Hash計算
但是你會發現相鄰的兩個子串資料之間是有重疊的，比如
dab
跟
abc
重疊了
ab
。這樣哈希下一個資料的Hash值其實可以借鑒下上一個資料的值推導得出：
優化計算哈希值
RK算法的時間複雜度包含兩部分，第一部分是周遊所有子串計算Hash值，時間複雜度是O(n)。第二部分是比較哈希值，這部分時間複雜度也是O(n)。
這個算法的核心就是盡量減少哈希值相等的情況下資料不一樣進而進行的比較，是以雜湊演算法要盡可能的好，如果你感覺用123對應字母abc容易碰撞，那用素數去比對也是OK的，反正目的是一樣的， 你可以認為這是一種取巧的辦法來處理字元串比對問題。
3 Boyer-Moore 算法。
Boyer Moore算法是一種非常高效的字元串比對算法，它的性能是著名的 KMP 算法的 3 到 4 倍。它不太好了解，但确是工程中使用最多的字元串比對算法。以前我們比對字元串的時候是一個個從前往後挪動來逐次比較，BM 算法核心思想是在模式串中某個字元與主串不能比對時，将模式串往後多滑動幾位，來減少不必要的字元比較。
移動比較對比
整體而言BM算法還是挺複雜的相比前面兩種，主要包含
壞字元規則
好字尾規則
。
3.1 壞字元規則
壞字元規則意思是根據模式串從後往前比對，當我們發現某個字元沒法比對的時候。我們把這個沒有比對的主串中的字元叫作壞字元。
壞字元
找到壞字元c後，在模式串中繼續查找發現c跟模式串任何字元無法比對，則可以直接将模式串往後移動3位。繼續從模式串尾部對比。
移動2格
此時發現壞字元是g，但在模式串中有個g存在，不能再往後移動3個了，移動的位置是2個。再繼續比對。那有啥規律呢？
發送不比對時，壞字元對應的模式串字元下标位置Si，如果壞字元在模式串中存在，取從後往前最先出現的壞字元下标記為Xi(取第一個是怕挪動太大咯)，如果壞字元在模式串中不存在則Xi = -1。此時模式串往後移動位數= Si - Xi。
壞字元移動規則
如果碰到極緻的主串=cccdcccdcccd，模式串=cccc，那此時時間複雜度是O(n/m)。
最優解
但是不要高興太早！下面這種情況可能導緻模式串不往後移動，反而往前移動哦！
往前移動？
是以此時BM算法還需要用到
好字尾規則
3.2 壞字元代碼
為避免每次都拿懷字元從模式串中周遊查找，此時用到散清單将模式串中每個字元及其下标存起來，友善迅速查找。
接下來說下散清單規則，比如一個字元是一個位元組，用大小為256的數組記錄每個字元在模式串出現位置，數組中存儲的是模式串出現的位置，數組下表是字元對應的ASCII值。
哈希規則
壞字元規則：
// 全局變量 SIZE
private static final int SIZE = 256;
// b=模式串數組，m是模式串數組長度，sl是哈希表，預設-1
private void generateBC(char[] b, int m, int[] sl) {
for (int i = 0; i < SIZE; i++) {
sl[i] = -1; // 初始化sl
}
for (int i = 0; i < m; ++i) {
int ascii = (int)b[i];
sl[ascii] = i;
}
}
接下來先不考慮好字尾規則跟壞字元的負數情況，先大緻寫出 BM 算法代碼。
壞字元BM
public int bm(char[] a, int n, char[] b, int m) {
// 記錄模式串中每個字元最後出現的位置
int[] sl = new int[SIZE];
// 建構壞字元哈希表
generateBC(b, m, sl);
// i表示主串與模式串對齊的第一個字元
int i = 0;
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; j--) {
if (a[i+j] != b[j]) break;
}
if (j < 0) {
// 比對成功，傳回主串與模式串第一個比對的字元的位置
return i;
}
//将模式串往後滑動j-bc[(int)a[i+j]]位
i = i + (j - sl[(int)a[i+j]]);
}
return -1;
}
3.3 好字尾規則
好字尾跟壞字尾道理類似，從後往前比對，直到遇到不比對的字元x，那主串x之前的就叫好字尾。
好字尾定義
此時移動的規則如下：
- 如果好字尾在模式串中找到了，用x框起來，然後将x框跟好字尾對齊繼續比對。 找到了移動規則
字元串硬核講解 - 找不到的時候，如果直接移動長度是模式串m位，那極有可能過度了！而過度移動存在的原因就是，比如你找了好字尾u，u在模式串中整體沒找到，但是u的子串d是可以跟模式串比對上的啊。 過度移動
字元串硬核講解
是以此時還要看好字尾的字尾子串是否跟模式串中的字首子串比對，從好字尾串的後字尾子串中找個最長能跟模式串的字首子串比對的然後滑動到一起，比如上面的d。
然後分别計算壞字元往後滑動位數跟好字尾往後滑動此時，兩者取其大作為模式串往後滑動位數，這種情況下還可以避免壞字元的負數情況。
3.4 好字尾代碼
好字尾的核心其實就在于兩點：
- 在模式串中，查找跟好字尾比對的另一個子串。
- 在好字尾的字尾子串中，查找最長的、能跟模式串字首子串比對的字尾子串。
3.4.1 預處理工作
上面兩個核心點可以在代碼層面用暴力解決，但太耗時！我們可以在比對前通過預處理模式串，預先計算好模式串的每個字尾子串，對應的另一個可比對子串的位置。
先看
如何表示模式串中不同的字尾子串
，因為字尾子串的最後個字元下标為m-1，我們隻需記錄字尾子串長度即可，通過長度可以确定一個唯一的字尾子串。
子串表示
再引入關鍵的變量
suffix
數組。suffix 數組的index表示字尾子串的長度。下标對應的數組值存儲的是
好字尾在模式串中比對的起始下标值：
suffix數組定義
比如此處字尾子串c在模式串中另一個比對開始位置為2， 字尾子串bc在模式串中另一個比對開始位置為1 字尾子串dbc在模式串中另一個比對開始位置為0， 字尾子串cdbc在模式串中隻出現了一次，是以為-1。
prefix 數組
這裡需注意，我們不僅要在模式串中查找跟好字尾比對的另一個子串，還要在好字尾的字尾子串中查找
最長的能跟模式串字首子串比對的字尾子串。比如下面：
最長模式比對
用
suffix
隻能查找跟好字尾比對的另一個子串。但還需要個 boolean 類型的
prefix
數組來記錄模式串的字尾子串是否能比對模式串的字首子串。
接下來重點看下如何填充
suffix
prefix
數組，拿下标從 0 到 i 的子串與整個模式串，求公共字尾子串，其中i=[0,m-2]。如果公共字尾子串的長度是 k，就suffix[k]=j，其中 j 表示公共字尾子串的起始下标。如果 j = 0，說明公共字尾子串也是模式串的字首子串，此時 prefix[k]=true。
suffix跟prefix數組
// b=模式串，m=模式串長度，suffix，prefix 數組 如上定義
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
//初始化
for (int i = 0; i < m; i++) {
suffix[i] = -1;
prefix[i] = false;
}
// b[0, i]
for (int i = 0; i < m - 1; i++) {
int j = i;
// 公共字尾子串長度
int k = 0;
// 與b[0, m-1]求公共字尾子串，并且會有覆寫現象産生。
while (j >= 0 && b[j] == b[m-1-k]) {
--j;
++k;
//j+1表示公共字尾子串在b[0, i]中的起始下标
suffix[k] = j+1;
}
//如果公共字尾子串也是模式串的字首子串
if (j == -1) prefix[k] = true;
}
}
3.4.2 正式代碼
有了
suffix
prefix
數組後，看下移動規則。假設好字尾串長度=k，如果k != 0，說明有好字尾，接下來通過suffix[k]的值來判斷如何移動。
- suffix[k] != -1，不等于時說明比對上了，模式串後移 j-suffix[k]+1 位，其中 j 表示壞字元對應的模式串中的字元下标。
- suffix[k] = -1，等于時說明好字尾沒比對上，那就看下子串的比對情況，好字尾的字尾子串長度是 b[r, m-1]，其中 r = [j+2,m-1]，字尾子串長度 k=m-r，如果 prefix[k] = true，說明長度為 k 的字尾子串有可比對的字首子串，這樣我們可以把模式串後移 r 位。
- 如果都沒比對上，那就直接将模式串後移m位。
// a跟n 分别表示主串跟主串長度。 // b跟m 分别表示模式串跟模式串長度。 public int bm(char[] a, int n, char[] b, int m) { // 用來記錄模式串中每個字元最後出現的位置 int[] sl = new int[SIZE]; // 建構壞字元哈希表 generateBC(b, m, sl); int[] suffix = new int[m]; boolean[] prefix = new boolean[m]; // 建構 suffix 跟 prefix 數組 generateGS(b, m, suffix, prefix); int i = 0; // j表示主串與模式串比對的第一個字元 while (i <= n - m) { int j; // 模式串從後往前比對 for (j = m - 1; j >= 0; --j) { // 壞字元對應模式串中的下标是j if (a[i+j] != b[j]) break; } if (j < 0) { // 比對OK ，傳回主串與模式串第一個比對的字元的位置 return i; } // 壞字元計算所得需移動長度 int x = j - sl[(int)a[i+j]]; int y = 0; // j < m-1 說明有好的比對上了 if (j < m-1) { y = moveByGS(j, m, suffix, prefix); } i = i + Math.max(x, y); } return -1; } // j = 壞字元對應的模式串中的字元下标 // m = 模式串長度 private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) { // 好字尾長度 int k = m - 1 - j; if (suffix[k] != -1) { // 好字尾可以比對上，傳回需移動長度 return j - suffix[k] + 1; } // 有比對到好字尾子串的模式串字首子串 for (int r = j+2; r <= m-1; ++r) { if (prefix[m-r] == true) { return r; } } // 沒找到直接 移動最大值 return m; }
3.5 複雜度分析
整個BM算法用到了額外的 sl、suffix、prefix三個數組，其中sl數組大小跟字元集大小有關，suffix 數組和 prefix 數組的大小跟模式串長度 m 有關。如果處理字元集很大的字元串比對問題，bc 數組對記憶體的消耗就會比較多。
因為好字尾和壞字元規則是獨立的，如果我們運作的環境對記憶體要求苛刻，可以隻使用好字尾規則，不使用壞字元規則，這樣就可以避免 bc 數組過多的記憶體消耗。不過，單純使用好字尾規則的 BM 算法效率就會下降一些了。
BM 算法的時間複雜度分析起來是非常複雜，一般在3n~5n之間。
4 KMP 算法
KMP算法跟BM算法類似，從前往後比對，把能比對上的叫
好字首
，不能比對上的叫
壞字元
KMP比對定義
遇到壞字元後就要進行主串好字首字尾子串跟模式串的字首子串進行對比，問題是對于已經比對過的好字首，能否找到一種規律，将模式串一次性滑動很多位？
暴力破解
思路是将主串中好字首的字尾子串和模式串中好字首的字首子串進行對比，擷取模式串中最大可以比對的字首子串。一般把好字首的所有字尾子串中，最長的可比對字首子串的那個字尾子串，叫作最長可比對字尾子串。對應的字首子串，叫作最長可比對字首子串。假如現在最長可比對字尾子串 =
u
，最長可比對字首子串 =
v
，獲得
u
v
的長度為
k
，此時在主串中壞字元位置為
i
，模式串中為
j
，接下來将模式串後移
j-k
位，然後将待比較的模式串位置
j = j-k
進行比較。
KMP算法移動
4.1 Next 數組存在意義
那最長可比對字首跟字尾我們用模式串就可以求解了。仿照BM算法，預先計算好就行。在KMP算法中提前構造個next數組。其中next數組的下标用來存儲字首子串最後一個資料的index，對應的value儲存的是這個字元串的字尾子串集合跟字首子串集合的交集。
幹說可能不太好了解，我們以"abababca"為例。它的部分比對表(Partial Match Table)數組如下：
Next數組
接下來對value值的擷取進行解釋，如果字元串A和B，存在A=BS，其中S是任意的非空字元串，那就稱B為A的字首。例如”what”的字首包括{"w","wh","wha"}，我們把所有字首組成的
字元串的字首集合。同樣可以定義字尾A=SB， 其中S是任意的非空字元串，那就稱B為A的字尾，例如"Potter"的字尾包括{"otter", "tter", "ter", "er", "r"}，然後把所有字尾組成字元串的字尾集合。要注意
字元串本身并不是自己的字尾。
PMT數組中的值是字元串的字首集合與字尾集合的交集中最長元素的長度。例如，對于"aba"，它的字首集合為{"a", "ab"}，字尾集合為{"ba", "a"}。兩個集合的交集為{"a"}，那麼長度最長的元素就是字元串"a"了，長度為1，是以"aba"的Next數組value = 1，同理對于"ababa"，它的字首集合為{"a", "ab", "aba", "abab"}，它的字尾集合為{"baba", "aba", "ba", "a"}， 兩個集合的交集為{"a", "aba"}，其中最長的元素為"aba"，長度為3。
我們以主串"ababababca"中查找模式串"abababca"為例，如果在
j
處字元不比對了，那在模式串[0,j-1]的資料串"ababab"中，字首集合跟字尾集合的交集最大值就是長度為4的"abab"。
PMT數組使用方法
基于此就可以使用PMT加速字元串的查找了。我們看到如果是在
j
位失配，那麼影響
j
指針回溯的位置的其實是第
j−1
位的 PMT 值，但是程式設計中為了友善一般不直接使用PMT數組而是使用Next數組，Next數組的value其實就是存儲的這個字首的最長可以比對字首子串的結尾字元下标，其中如果比對不到用-1代替。
Next數組使用
4.2 KMP 比對代碼
// a = 主串，n=主串長度。b = 模式串，m = 模式串長度
public static int kmp(char[] a, int n, char[] b, int m) {
int[] next = getNexts(b, m);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && a[i] != b[j]) {
j = next[j - 1] + 1; // 發現不一樣則 保持i 不變 j進行移動
}
if (a[i] == b[j]) {
++j;
}
if (j == m) { // 找到比對模式串的了
return i - m + 1;
}
}
return -1;
}
至此你會發現隻要搞明白了
PMT
存在的意義，然後順着思路推
Next
數組即可。
4.3 Next 數組求解
當要計算next[i]時，前面計算過的next[0~i-1]是否可以被用來快速推導出next[i]呢？
情況一：如果next[i-1] = k-1，那此時b[0,i-1]的最長可比對字首子串是b[0,k-1]，如果b[0,i-1]的下個字元b[i]跟b[0,k-1]的下個字元b[k]相等，那next[i] = k。
情況二：假設b[0,i]最長可用字尾子串是b[r,i]，那b[r,i-1]肯定是b[0,i-1]的可比對字尾子串，但不一定是最長可比對字尾子串。比如字元串b = "dexdecdexdex"，此時最長可比對字尾子串是"dex"，b去掉最後的'x'成為B，此時雖然"de"是B的可比對字尾子串，但"dexde"才是最長字尾子串！也就是說b[0, i-1]最長可比對字尾子串對應的模式串的字首子串的下一個字元并不等于 b[i]。
那此時看下b[0,i-1]的
次長
可比對字尾子串b[x,i-1]對應的可比對字首子串b[0,i-1-x] 的下個字元b[i-x] 是否等于b[i]，相等那b[0,i]的最長可比對字尾子串是b[x,i]。
那我們來求 b[0, i-1]的次長可比對字尾子串呢？次長可比對字尾子串一定被包含在最長可比對字尾子串中，而最長可比對字尾子串又對應最長可比對字首子串 b[0, y]。此時查找 b[0, i-1]的次長可比對字尾子串變成了查找b[0, y]的最長比對字尾子串的問題。
按此思路考察完所有的 b[0, i-1]的可比對字尾子串 b[y, i-1]，直到找到一個可比對的字尾子串，它對應的字首子串的下一個字元等于 b[i]，那這個 b[y, i]就是 b[0, i]的最長可比對字尾子串。
// b = 模式串，m = 模式串的長度
private static int[] getNexts(char[] b, int m) {
int[] next = new int[m];
next[0] = -1;
int k = -1;
for (int i = 1; i < m; ++i) {
while (k != -1 && b[k + 1] != b[i]) {
k = next[k];
// 因為前一個的最長串的下一個字元不與最後一個相等，需要找前一個的次長串，
// 問題就變成了求0到next(k)的最長串，如果下個字元與最後一個不等，
// 繼續求次長串，也就是下一個next(k)，直到找到，或者完全沒有
// 最好結合前面的圖來看
}
if (b[k + 1] == b[i]) {
++k; // 字元串相等則看下一個
}
next[i] = k; // 數組指派
}
return next;
}
KMP空間複雜度：該算法隻需要一個額外的 next 數組，數組的大小跟模式串相同。是以空間複雜度是 O(m)，m 表示模式串的長度。
KMP時間複雜度：next 數組計算的時間複雜度是 O(m) + 比對時候時間複雜度是 O(n) = O(m+n)
至此，常見的字元串比對算法正式講解完畢，其實前面說的都是一個主串，一個模式串。如果感興趣你也可以看下AC自動機，該算法可實作周遊一次主串同時比對多個模式串，屬于ＫＭＰ的更新版，在平常字元串比對的時，用途廣泛。本文核心思路借鑒極客時間小争哥的資料結構跟算法課程，課程品質相當高，作為自來水推薦一波，有想購買的私聊我，有優惠哦。
5 參考