KMP算法測試

KMP 算法詳解

根據解釋寫出對應的C++代碼進行測試，也可以再整理成一個函數

#include <iostream>
#include <vector>class KMP
{
private:std::string m_pat;//被匹配的字符串std::vector<std::vector<int>> m_dp;//狀態二維數組public:void create_dp(std::string pat){int M = pat.length();//dp[狀態][下一字符] = 下一狀態std::vector < std::vector<int> > dp(M, std::vector<int>(256, 0));//初始化全部為0//base case 遇到第一個匹配的字符就轉到狀態1dp[0][pat.at(0)] = 1;//影子狀態X初始在0狀態int X = 0;//構建狀態轉移圖，確定每一個狀態遇到任何字符后狀態的轉變for (int i = 1; i < M; i++){//每一個狀態遇到任何字符的處理,字符的大小不超過256for (int j = 0; j < 256; j++){//先把當前狀態遇到所有字符后的狀態，與影子的狀態一致dp[i][j] = dp[X][j];}//遇到正確的字符，再單獨調整，直接跳轉下一狀態dp[i][pat.at(i)] = i + 1;//更新影子的位置，遇到一樣的字符后，才會更新X = dp[X][pat.at(i)];}this->m_dp = dp;//保存為私有this->m_pat = pat;//保存為私有}//在txt里面搜索pat,成功了返回匹配的索引int search(std::string txt){int M = this->m_pat.length();int N = txt.length();//pat 的初始狀態為0，表示還沒有一個處理成功int j = 0;for (int i = 0; i < N - M; i++){//計算pat的下一狀態j = this->m_dp[j][txt.at(i)];//到達終點的狀態，全部匹配成功if (j == M)return i - M + 1;}//沒有到達終點狀態，匹配失敗return -1;}
};int main()
{KMP kmp;kmp.create_dp("aaaabaaa");//創建需要被匹配的字符串int res = kmp.search("aaaabaabaaaabaaa");//開始在指定的字符串里面搜索if (res < 0)printf("未能匹配！\n");printf("匹配成功，索引為：%d", res);return 0;
}