KMP演算法
KMP演算法是一種高效的字串匹配演算法，在傳統暴力遍歷匹配的基礎上做了一定的優化，
首先KMP演算法的實作也是使用了回退思想，不過與暴力遍歷不同，KMP的回退，是讓子串進行匹配，而不是主串，
KMP示例
首先我們來看兩個例子來理解KMP演算法：
例1：
分別從str的i和sub的j位置處開始匹配：
此時a與c不匹配，如果暴力遍歷的話，是i回到到b，j也回到a，重新一輪匹配，而KMP演算法，是將子串的j回到第二個a，str[i]與sub[j]重新開始匹配，原因很明顯，第二個ab與第一個ab是相同的，因為這一部分主串與子串是匹配的，所以在主串中也是這樣，因而主串的后半部分的ab就匹配了子串的前半部分ab，就省去了再重新匹配的程序，直接繼續之前的部分匹配結果再向后匹配，
繼續匹配：
再看一個例2：
開始匹配：
我們看到，此時a 與 c不匹配，如果暴力遍歷的話，是i回到到b，j也回到a，重新一輪匹配，而KMP演算法，是將子串的j回到a，str[i]與sub[j]重新開始匹配，
很多人可能疑問，為什么是這樣？好像很有道理的樣子
我們仔細觀察，在子串中，j所指的c之前，除了最開頭的a，找不到已經與主串匹配好了的字串ab或者是a(要與c相鄰)，**注意，是除了最開頭的a，**正是因為在這段區間找不到ab或a，所以才從頭再開始遍歷，i不動，因為在i前面的主串中已經找不到與abc(子串的前三個字符)匹配的字串了，
j回到最開始后，再開始匹配：
與之前一樣，在j所指的d之前，除了最開頭的a，找不到與主串已經匹配好了的abc或ab或a，所以j又要重新回頭，到最開始，
再次遍歷：
KMP核心
看完上述程序后，我們要實作這種讓子串回頭的方法，就是定義一個next陣列，里面對應子串中每一個字符出現不匹配情況時，要回頭到達的位置，
KMP 的精髓就是 next 陣列：也就是用 next[j] = k;來表示，每個j 都對應一個 K 值， 這個 K 就是將來j要移動時，要移動到的位置，
而 K 的值是這樣求的：
1、規則：找到匹配成功部分的兩個相等的真子串(不包含本身)，一個以下標 0 字符開始，另一個以 j-1 下標字符結尾，
2、不管什么資料，next[0] = -1;next[1] = 0;
3、如果找得到，則k值等于相等的子串的長度；如果找不到，則k值等于0，即回到a
以例1中的子串為例：ababc
我們默認第一個和第二個字符出現不匹配情況時，next陣列中存的值分別是-1和0，即，a不匹配時，k == -1，則需要主串的i向后走一步(這里先解釋，可以到代碼實作的時候再理解)，b不匹配時，回到a重新匹配，
第三個字符a如果出現不匹配情況，我們找已經匹配的相等的兩個子串：以a開頭的字串，與以b結尾的字串，很明顯找不到，所以它要回到a，k = 0
第四個字符b出現不匹配情況時，同樣找已經匹配的相等的兩個子串：以a開頭的字串，以a結尾的字串，可以找到字串a，所以k = 1，即回到b
第四個字符c出現不匹配情況時，找已經匹配的相等的兩個子串：以a開頭的字串，以a結尾的字串，可以找到ab，所以k = 2，即回到第二個a
至此，子串的next陣列就為：[-1, 0, 0, 1, 2]
兩道求next陣列的練習：
練習 1： ”ababcabcdabcde”
next陣列：-1 0 0 1 2 0 1 2 0 0 1 2 0 0
練習 2： ”abcabcabcabcdabcde”
next陣列：-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0
建議大家自主完成，這有助于我們后面的理解
next陣列求解
那么，如何用代碼求出next陣列呢？
求sub[j]的k值
1、當sub[j-1] == sub[k]時(k為sub[j-1]的k值)
同樣以ababc為例
我們已知前面四個字符的next陣列為:[-1, 0, 0, 1 ]，求c的k值
如果按照上面的求法，我們知道k = 2，但仔細觀察，c前面的b，即sub[j - 1]，與第二個字符b，即sub[k]相同(該k為前一個字符b的k值)，第二個b之前已經匹配的子串aba中，兩個符合要求的相等的子串為a，而現在的匹配的子串為abab，這兩個b相等，在前面字符k值的基礎上，c的k值就可以簡單地看成是前一個字符的k + 1，即c的k == 1+1 = 2
2、當sub[j-1] != sub[k]時
以ababcd為例
我們已知ababcd的前五個字符的next陣列:[-1, 0, 0, 1, 2]，求d的k值
很明顯，在已經匹配的子串ab中，找不到相等的兩個子串：以a開頭的字串，以c結尾的字串，所以d要回退到最開始的a處，
此時的j指向d，且sub[j - 1] != sub[k]，即c != a，d應該回退到元素sub[k] (即第二個a)的k值處，也就是d的k == next[k] = 0
代碼實作：
1、求出next陣列
分兩種情況：
- sub[j-1] == sub[k]
- sub[j-1] != sub[k]
還有一種情況之前我們沒有提到，就是回退到了最開始元素的k值處，即-1.此時說明主串中的字符與j及j之前的所有字串都不匹配，所以需要向后走一步，從下一個字符再重新開始匹配
void GetNext(vector<int>& next, const string& subStr, int n)
{
//默認處理
next[0] = -1;
next[1] = 0;
int i = 2;//從第3個元素開始處理
int k = 0;//表示i的前一個元素的next陣列元素值
while (i < n)
{
//可能回退至首元素了,說明當前元素需要重新匹配，即從首元素開始，所以也是k = k + 1
if (k == -1 || subStr[i - 1] == subStr[k])//P[i - 1] == P[k]
{
k = k + 1;
next[i] = k;
i++;
}
else//不匹配則回退
{
k = next[k];
}
}
}
2、匹配邏輯的實作
與暴力求解類似，只不過當字符不相等時，不是雙方都回頭，而是子串回頭，正因為子串會回退，當回退的下標j == -1時，表明主串需要向后走，
完整代碼：
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void GetNext(vector<int>& next, const string& subStr, int n)
{
next[0] = -1;
next[1] = 0;
int i = 2;
int k = 0;//表示i的前一個元素的next陣列元素值
while (i < n)
{
//可能回退至首元素了,說明主串需要向后走，子串從首元素開始，所以也是k = k + 1
if (k == -1 || subStr[i - 1] == subStr[k])//P[i - 1] == P[k]
{
k = k + 1;
next[i] = k;
i++;
}
else//不匹配則回退
{
k = next[k];
}
}
}
int KMP(const string& str, const string& subStr, int pos)//從主串的str位置開始匹配
{
int strLength = str.size();
int subLength = subStr.size();
if (str.empty() || subStr.empty()) { return -1; }
if (pos >= strLength || pos < 0) { return -1; }
vector<int> next(subLength);//子串的next陣列
GetNext(next, subStr, subLength);
int stri = pos;//遍歷str
int subj = 0;//遍歷subStr
while (stri < strLength && subj < subLength)
{
//回退至子串第一個元素還未匹配，或者正常匹配，都需要將兩個坐標+1
if (subj == -1 || str[stri] == subStr[subj])
{
stri++;
subj++;
}
else//不匹配了，回退
{
subj = next[subj];
}
}
if (subj == subLength)//說明匹配到位了
{
//回傳主串的起始匹配位置
return stri - subLength + 1;
}
return -1;
}
next陣列的優化
以子串aaaaaaaab為例，它的next陣列為:[-1, 0, 1, 2, 3, 4, 5, 6, 7]當主串字符str[i] != 子串中的最后一個a時，匹配的字符回退到下標6的字符a，此時str[i]還是 != a，所以依舊需要回退，一直回退到第一個字符a
對于這種情況，我們可以做一個優化，當回退的字符s2與當前字符s1相同，則繼續回退至s2的k值處，一直回退到不相等或者最開始處，所以s1的k值就等于s2的k值，
練習：模式串 t=‘abcaabbcabcaabdab’ ，該模式串的 next 陣列的值為（ D ） ， nextval 陣列的值為 （F），
A． 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B． 0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
C． 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D． 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
E． 0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F． 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
注意：這里是將第一個元素和第二個元素的初始k值設定為0和1，所以我們只要把求出的結果+1即可
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/385663.html
標籤：其他