暴力匹配就不說了，說說KMP，
KMP演算法思想：
- 第一步：根據模式串(needle)得出next陣列，
- 第二步：匹配主串，但在匹配主串時，遇到沖突位置時，不是立即和暴力匹配一樣直接從頭匹配，而是查看next陣列，得到一個回退位置，從此處再開始匹配，
- 重復第二步，直至匹配成功或者匹配失敗，
next陣列：
這里我選擇next陣列為最初始狀態，不做調整(例如全部-1或者右移一個補-1)
長度為needle.size()，
next[i]表示從next[0]~next[i]構成的字串中最長前后公共子串的長度，此外，這個這個長度剛好是前公共子串最后一個位置的后一個index，也就是如果此處匹配失敗，回退的目標index就是這個index，
特別的，next[0] = 0；
具體求next
void creatNextArray(string str, vector<int>& next)
{
int n = str.size();
next[0] = 0;
int j = 0;//前綴末尾index
int i;//后綴末尾index
for (i = 1; i < n; ++i)
{
while (j > 0 && str[i] != str[j])
{
j = next[j - 1];
}
if (str[i] == str[j])
{
++j;//使j為公共子串最后一個位置的后一個index，恰好也是子串的長度
}
next[i] = j;
}
}
前綴末尾從0開始，后綴末尾從1開始，遍歷整個needle,當i和j指向的值不等，那么需要j回退至next[j-1]（注意，這里的next未作特殊處理，即跳轉的位置需查前一個位置的next值，），并且需要重復此操作，隨后判斷是否匹配上，匹配上則把j右移，填上next[i]，
匹配
逐一匹配，匹配，則往下走，沖突，則讓needle的index回退到next[index-1]，
重復上述操作，直至匹配完畢，
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
if(m==0) return 0; //模式字串為空
vector<int> next(m);
createNext(needle,next);
int j = 0;
for(int i = 0; i < n; ++i)
{
while(j>0&&needle[j] != haystack[i])
{
j = next[j-1];
}
if(needle[j]==haystack[i])
{
++j;
}
if(j==m) return i-m+1;//haystack[i]剛好匹配上了needle最后一個，i-m+1就是匹配needle[0]的那個index
}
return -1;//沒找到
}
值得一提的時，KMP演算法會在特殊情況下，效率急劇下降，
KMP主要靠回退減少匹配次數，但如果回退次數非常多，即回退后發現還是不匹配，又回退，特別是當回退時因為匹配同一個字符而導致回退，我們明知道這個字符匹配不上，回退之后又是這個字符，那應該直接跳過它，而不是又匹配一次，
因此優化的方式為，在計算next陣列時，如果當前索引對應的字符和回退之后的索引的字符相同，那么直接將當前索引的next值，置為回退之后索引的next值，快速回跳，
以下為整體代碼
#include<iostream>
#include<vector>
using namespace std;
void creatNextArray(string str, vector<int>& next)
{
int n = str.size();
next[0] = 0;
int j = 0;//前綴末尾index
int i;//后綴末尾index
for (i = 1; i < n; ++i)
{
while (j > 0 && str[i] != str[j])
{
j = next[j - 1];
}
if (str[i] == str[j])
{
++j;
}
//下方注釋為優化做法
//next陣列的決策不同，實作不同，優化的代碼就會有不同，理解如何優化即可
/*if (i < n - 1 && j>0 && str[i + 1] == str[next[j - 1]]) next[i] = next[j - 1];
else next[i] = j;*/
next[i] = j;
}
}
int main()
{
string a("ababababababc");
string b("abababc");
int n = b.size();
int m = a.size();
vector<int> next(n);
creatNextArray(b, next);
int j = 0;
int ans = -1;
for (int i = 0; i < m; ++i)
{
while (j > 0 && a[i] != b[j])
{
j = next[j - 1];
}
if (a[i] == b[j])
{
++j;
}
if (j == n)
{
ans = (i - n + 1);
}
}
cout << ans<<endl;
return 0;
}
實測效率上，二者差不太多，查看next陣列，優化后的next也確實有了回跳的對應資料，可能一個是資料比較小(雖然也試過達到5000+的字符)，一個是即使重復回跳，但由于僅僅只有一個賦值操作，甚至編譯器可能會進行優化，導致效率差距不大，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278379.html
標籤：其他
上一篇：讓串口和Modbus初始化的引數同步起來-STM32F103、FreeModbus從站設計（6）
下一篇：資料流中數字的秩