#include <iostream> #include<vector> #include<string> #include <unordered_map> #include <unordered_set> #include <queue> #include <algorithm>//算法頭文件 #include <numeric> #include <stack> #include<typeinfo>#include<stdio.h> using namespace std;class KMP { private:vector<vector<int>> dp;//二維狀態(tài)轉(zhuǎn)移數(shù)組string pat;//模式串 public:KMP(string _pat) {pat = _pat;int len = pat.size();//狀態(tài)轉(zhuǎn)移數(shù)組dp.resize(len, vector<int>(256));//指定大小后 默認(rèn)值為0//邊界條件 在0狀態(tài)時(shí)只有遇到了pat[0]才能轉(zhuǎn)到狀態(tài)1dp[0][(int)pat[0]] = 1;//初始化影子狀態(tài)初始值int X = 0;//構(gòu)建狀態(tài)轉(zhuǎn)移圖for (int j = 1; j < len; j++) {for (int c = 0; c < 256; c++) {if(c != (int)pat[j])dp[j][c] = dp[X][c];?? ??? ??? ?//如果遇到的字符c與j狀態(tài)需要進(jìn)行推進(jìn)所匹配的字符不匹配時(shí) 就狀態(tài)重啟到影子狀態(tài)elsedp[j][c] = j + 1;?? ?//如果遇到的字符c與j狀態(tài)需要進(jìn)行推進(jìn)所匹配的字符相匹配時(shí) 將進(jìn)行狀態(tài)推進(jìn)//也可以對(duì)上面的if進(jìn)行優(yōu)化如下面注釋的兩行//dp[j][c] = dp[X][c];?? ??? ??? ?//如果遇到的字符c與j狀態(tài)需要進(jìn)行推進(jìn)所匹配的字符不匹配時(shí) 就狀態(tài)重啟到影子狀態(tài)//dp[j][(int)pat[j]] = j + 1;?? ?//如果遇到的字符c與j狀態(tài)需要進(jìn)行推進(jìn)所匹配的字符相匹配時(shí) 將進(jìn)行狀態(tài)推進(jìn)}//更新影子狀態(tài)X = dp[X][(int)pat[j]];}}int search(string txt) {int len = txt.size();//pat串的初始狀態(tài)為0int j = 0;for (int i = 0; i < len; i++) {//計(jì)算j的下一個(gè)狀態(tài)j = dp[j][(int)txt[i]];//如果狀態(tài)到達(dá)終止態(tài)(到pat末尾時(shí))if (j == pat.size()) return i - pat.size() + 1;}//如果遍歷完txt還沒到達(dá)終止態(tài)則匹配失敗return -1;} };int main() {string pat = "aaab";//ababc ?aaabstring txt = "aaaaaaab"; //aaaaaaab ?aaacaaabKMP aa(pat);int pos1 = aa.search(txt);cout << pos1 << endl;system("pause");return 0; }

?

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的C++ KMP算法完整实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。