溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了使用c++ 如何實現KMP算法，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
KMP
KMP算法解決的問題
字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中開始的位置。
如何做到時間復雜度O(N)完成？
思路：
首先判斷兩個字符串是否為空串，并且str2的長度是否小于str1的長度，因為題目要求str1中包含str2。
以上都滿足的情況下，首先定義兩個變量分別為 x ，y 作為后續字符串中字符遍歷的下標，然后再生成一個vector容器next，用來后續的匹配加速
然后在str2中，做加速操作，也就是 看當前 i - 1和之前的所有字符，有沒有相同的，最大匹配長度。
從上圖可以看到，下標0和1位置的值永遠都是固定的-1和0,。
x 字符是 i 位置，x 前面的 c 是 i - 1 位置，也就是從下標0位置到5位置，找最大的匹配長度，然后填到 i 的next中。這是循環中的case1
如果當next中的值大于0的時候，從b開始，找到next中的2位置，然后跳轉到當前位置的next中的坐標上，接著進行匹配。
最后如果到next為0或者-1的位置上，就標記當前位置為0，然后到下一個坐標繼續判斷。
當 i 遍歷完str2后，循環結束，代表next中的值已經全部設置好了。
當str1 和 str2 沒有循環遍歷到尾部的時候，只要 str1 中 x 的位置 等于 str2 中 y 的位置 ，x 和 y 就同時自增。
如果next中的值等于 -1 ，就說沒有匹配成功，x 單獨自增。讓str1往后挪一位
如果str2中的沒有匹配成功，就往前找next數組的值，只要不等于 -1 ，就一直執行這個往前移的過程。
最后看 y 是否已經到了str2的位置，如果到了就說明找到了，直接返回 x的位置 減去 y的位置，就是匹配開始的位置，否則就是沒有找到，直接返回 -1
void getNextArray(string str, vector<int>& next)
{
if (str.length() == 1)
{
next.push_back(-1);
}
next.resize(str.length());
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while (i < next.size())
{
if (str[i - 1] == str[cn])
{
next[i++] = ++cn;
}
else if (cn > 0)
{
cn = next[cn];
}
else {
next[i++] = 0;
}
}
}
int getIndexOf(string s, string m)
{
if (s == "" || m == "" || s.length() < 1 || s.length() < m.length())
{
return -1;
}
int x = 0;
int y = 0;
vector<int> next;
getNextArray(m,next);
while (x < s.length() && y < m.length())
{
if (s[x] == m[y])
{
x++;
y++;
}
else if (next[y] == -1)
{
x++;
}
else {
y = next[y];
}
}
return y == m.length() ? x - y : -1;
}上述內容就是使用c++ 如何實現KMP算法，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
