KMP算法【C++】

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;
}