一、BF算法
Brute-Force簡稱BF算法，也稱單比對算法。采用窮舉的思路。BF是暴力的意思。
算法思路：從T的每一個字元開始依次與P的字元進行比對。
BF算法比對過程：
【代碼實作】
分析：
要完成對于所有字元的比對工作，可以周遊母串，并逐個與子串比較，若相同，則字串比對位後移，若不成功，回溯歸零（
i = i - j + 1
和
j = 0
），當比對成功長度等于字串長度，傳回結果.
【參考代碼】
#include<iostream>
#include<string>
using namespace std;
int BF(string a, string b)
{ int i= 0, j = 0;
while(i < a.length() && j < b.length())
{
if(a[i] == b[j])// 比對成功，同時移動
{
i ++;
j ++;
}
else // 比對不成功：回溯
{
i = i - j + 1;
j = 0;
}
}
if(j == b.length()) return i - j; // b字元比較完畢，傳回位置
else return -1;
}
int main(){
string s1, s2;
cin>> s1 >> s2;
cout<<BF(s1,s2); // P 在 T 中的起始位置
return 0;
}
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int BF(string a, string b)
{ int i = 0, j = 0; // i别忘了也要初始化
while(i < a.length() && j < b.length())
{
if(a[i] == b[j])// 比對成功，同時移動
{
i ++;
j ++;
}
else // 比對不成功：回溯
{
i = i - j + 1;
j = 0;
}
}
if(j == b.length()) return i - j; // b字元比較完畢，傳回位置
else return -1;
}
int main()
{
int t;
cin>>t;
while(t -- )
{
string a,b;
cin>>a>>b;
string b2 = b;
reverse(b2.begin(),b2.end());
string c = b + b2;
cout<<BF(a,c);
}
return 0;
}
【時間複雜度分析】
假設目标串規模為n，模式串規模為m
最好：O(m)
最壞：最壞的情況是每遍比較都在最後出現不等，即沒變最多比較m次，最多比較n-m+1遍。
總的比較次數最多為m(n-m+1)，是以BF算法的時間複雜度為O(mn)。
二、KMP算法
【KMP有什麼用】
KMP主要應用在字元串比對上。
KMP的主要思想是當出現字元串不比對時，可以知道一部分之前已經比對的文本内容，可以利用這些資訊避免從頭再去做比對了。
是以如何記錄已經比對的文本内容，是KMP的重點，也是next數組肩負的重任。
為了解決BF算法每次不比對 j都要回溯到起始位置問題，引入KMP算法
【kMp實作】
KMP具體代碼實作有兩種一種是next[]數組一種是prefix[]數組，其實用哪一種都可以，使用prefix就是使用字首表（上圖示）。使用next其實放的也是字首表，隻不過是在字首表的基礎上進行了一些調整（如後移一位或者統一減一）——初始位置變成
-1
。上面兩種數組統稱next[]數組當遇到沖突的時候next[]數組方式告訴我們要回退（回溯）到哪裡——（就不必要每次都要回到起點了）
【字首表】
字首表有什麼作用呢？
字首表是用來回退的，它記錄了模式串與主串(文本串)不比對的時候，模式串應該從哪裡開始重新比對。
要求字首表就先要知道什麼是字首什麼是字尾：
- 字首是指不包含最後一個字元的所有以第一個字元開頭的連續子串。
- 字尾是指不包含第一個字元的所有以最後一個字元結尾的連續子串。
可以看出，文本串中第六個字元b 和 模式串的第六個字元f，不比對了。如果暴力比對，會發現不比對，此時就要從頭比對了。
但如果使用字首表，就不會從頭比對，而是從上次已經比對的内容開始比對，找到了模式串中第三個字元b繼續開始比對。
字首表是如何記錄的呢？
首先要知道字首表的任務是目前位置比對失敗，找到之前已經比對上的位置，在重新比對，此也意味着在某個字元失配時，字首表會告訴你下一步比對中，模式串應該跳到哪個位置。
為什麼一定要用字首表呢？
字首表告訴我們 上次比對的位置，并跳過去！
回顧一下，剛剛比對的過程在下标5的地方，遇到不比對，模式串j + 1指向了f，如圖：
然後就找到了下标2，指向第二個a，繼續比對（p[j + 1] 與 s[i]）：如圖：
以下這句話，對于了解為什麼使用字首表可以告訴我們比對失敗之後跳到哪裡重新比對 非常重要！
下标5之前這部分的字元串（也就是字元串aabaa）的最長相等的字首 和 字尾字元串是 子字元串aa ，因為找到了最長相等的字首和字尾，比對失敗的位置是字尾子串的後面，那麼我們找到與其相同的字首的後面從新比對就可以了。
是以字首表具有告訴我們目前位置比對失敗，跳到之前已經比對過的地方的能力。
字首表的計算：了解定義就知道怎麼判斷啦
了解i與j（不比對j跳轉後）：
i ：指向字尾末尾的位置（上例指向b）
j： 指向字首末尾的位置、還代表着下标i之前（包括i）的字串的最長相等前字尾長度（上例為2）
next考慮的是所有非平凡字首和字尾，即考慮的字首和字尾都不是整個原串，至少要比原串短一個字元，是以i要從第二個字元開始枚舉
模闆
個人習慣下标是從1開始的
比對過程：
文本串(S串)：i從1開始（初始輸入時下标是從1開始的）
模式串(P串)：j從0開始，但實際比對的是j + 1
試圖與
S[i]
比對的是
P[j + 1]
(1~j位置的串就是字首)：
比對成功則
i、j
都移動;
比對不成功：
while(j && s[i] != p[j + 1]) j = ne[j]
：比對不成功則
j
回退到
next[j]
(字首表)直到
S[i]
與
P[j + 1]
比對為止，或者
j
為0（退無可退）循環截止
當 j = 模式串的長度時，比對成功
求next[]數組：
求ne過程和比對過程完全類似：
模式串i從2開始，i = 1時隻有一個數不存在前字尾，即next[1] = 0，故不用計算
j初始化為0，但比較的是p[i] 與 p[j + 1]
while (j && p[i] != p[j + 1]) j = ne[j];
當不比對時j回退到next[j]的位置（退而求其次，不斷嘗試直到ne[j]的下一個位置比對成功，ne[ne[j]]）...(j遞歸回溯求解的過程)，成功之後i、j往後走一步——最終j就是該位置的最長相等公共前字尾了
記錄下模式串每一位置上的ne結果：ne[i] = j
循環往複
// s[]是長文本，p[]是模式串，n是s的長度，m是p的長度
求模式串的Next數組：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 比對
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 比對成功後的邏輯
}
}
【acwing KMP字元串】
給定一個模式串 SS，以及一個模闆串 PP，所有字元串中隻包含大小寫英文字母以及阿拉伯數字。
模闆串 PP 在模式串 SS 中多次作為子串出現。
求出模闆串 PP 在模式串 SS 中所有出現的位置的起始下标。
輸入格式
第一行輸入整數 NN，表示字元串 PP 的長度。
第二行輸入字元串 PP。
第三行輸入整數 MM，表示字元串 SS 的長度。
第四行輸入字元串 SS。
輸出格式
共一行，輸出所有出現位置的起始下标（下标從 00 開始計數），整數之間用空格隔開。
資料範圍
1≤N≤1051≤N≤105
1≤M≤1061≤M≤106
輸入樣例：
輸出樣例：3
aba
5
ababa
0 2
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e7 + 10;
int ne[N];
char p[N], s[N];
int n, m;
int main()
{
cin>> n >> p + 1>> m >> s + 1;
// 求ne[]
for(int i = 2, j = 0; i <= n; i++)
{
while(j && p[i] != p[j + 1]) j = ne[j];
if(p[i] == p[j + 1]) j ++;
ne[i] = j;
}
// 比對過程:利用ne數組進行模式比對
for(int i = 1, j = 0; i <= m; i++)
{
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j ++;
// 比對成功
if( j == n)
{
j = ne[j];// 尋找p在s中的下一次出現的位置，利用ne數組優化時間複雜度
cout<<i - n<<" ";
}
}
return 0;
}
比對成功後： j = ne[j];
因為比對成功後，p[j + 1]相當于是空字元，一定不比對s[]中的任何字元，是以可以更新一次j；又或者是p串比在s串中多次出現，你還要繼續比對尋找起始位置
因為p[n + 1] == '\0'，它和s[]中的任何一個字元都不比對，是以這裡寫不寫都可以。但建議寫上，避免以後出現邊界問題
cin >> n >> p + 1 >> m >> s + 1
這樣讀入字元串的下标就從1開始！
三、C++ string中的find()函數
C++ string中的find()函數,通常會用來判斷母串中有無某一子串或者字元，比對的實作原理其實就是KMP算法
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s1, s2, s3, s4;
s1 = "ab";
s2 = "acabdef";
s3 = "cef";
s4 = "def";
//1. string中find()傳回子竄在母串中的的起始位置（下标記錄）
int t = s2.find(s1); // 傳回子竄在母串中的的起始位置 t = 2
cout<<t;
//2. 如果沒有找到，那麼會傳回一個特别的标記npos(也可以了解為-1)。（傳回值可以看成是一個int型的數）
if(s2.find(s3) == -1) cout<<"NO"<<endl;
else cout<<"YES"<<endl; //結果： NO
if(s2.find(s4) == -1) cout<<"NO"<<endl;
else cout<<"YES"<<endl; //結果： YES
return 0;
}