什么是KMP
?要做一個東西我們先要理解一個東西，KMP是什么，就是我的標題，字符串匹配。就這樣講可能不好理解，這里我們先拋出一個題目，下文就以這個題講講跟著理解一下。
KMP有什么好處
?上題大多數(shù)人剛剛?cè)腴T的人肯定會想到，暴力求解，下面也會提一下，但使用KMP的好處就是能夠消除了主串指針的回溯，從而使算法效率有了某種程度的提高。（了解一下就好）好了，進正題。
暴力解法（不是重點，帶過）
思路：假設現(xiàn)在文本串S匹配到 i 位置，模式串P匹配到 j 位置，則有：
如果當前字符匹配成功（即S[i] == P[j]），則i++，j++，繼續(xù)匹配下一個字符；
如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相當于每次匹配失敗時，i 回溯，j 被置為0。
int ViolentMatch(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{
if (s[i] == p[j])
{
//如果當前字符匹配成功（即S[i] == P[j]），則i++，j++
i++;
j++;
}
else
{
//如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
i = i - j + 1;
j = 0;
}
}
//匹配成功，返回模式串p在文本串s中的位置，否則返回-1
if (j == pLen)
return i - j;
else
return -1;
}
KMP算法
上題kmp算法如何做到在aabaabaah字符串中找到這個與模式串aabaah相匹配的子串的呢，就需要另一個概念，前綴表。
前綴表
?我們模式串a(chǎn)abaah在匹配時出現(xiàn)了aabaa匹配，到h不和b匹配了，那么從h的前面有一個模式串的子串a(chǎn)abaa，后綴是aa，找到與其相等的前綴也是aa，所以下一次匹配就從b開始。
這樣我們在匹配時遇到不匹配的字符時只需要找它前面的最長相等前后綴。
先來理清另一個概念，
**
前綴是包含首字母，不包含尾字母的所有子串都是前綴。
后綴只包含尾字母，不包含首字母的所有子串都是后綴。
用aabaah舉例。
| 前綴 | 后綴 |
|---|---|
| a | h |
| aa | ah |
| aab | aah |
| aaba | baah |
| aabaa | abaah |
** **
?上圖可以看到匹配時，遇到h不匹配了，如何看前面子串最長相等前后綴，就是h的前面一個a，長度是2，意義在于這個后綴的前面有一個相等長度為2的前綴，那么在這個后綴后面匹配不相等了就要在這個前綴的后面重新開始找匹配，而與其相等前綴的后面的那個下標，也就是b的下表，正好是2。
?一般情況都會做一個操作，右移或者全部減一使得起始位為-1，這里全部減一。兩種不同的kmp算法實現(xiàn)方式，不做此操作也可以，不涉及原理問題。
代碼實現(xiàn)
void kmp(int* next, const string& s){
next[0] = -1;
int j = -1;
for(int i = 1; i < s.size(); i++){
while (j >= 0 && s[i] != s[j + 1]) {
j = next[j];
}
if (s[i] == s[j + 1]) {
j++;
}
next[i] = j;
}
}
文章參考：代碼隨想錄，kmp算法
