#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;//二维状态转移数组
string pat;//模式串
public:
KMP(string _pat) {
pat = _pat;
int len = pat.size();
//状态转移数组
dp.resize(len, vector<int>(256));//指定大小后 默认值为0
//边界条件 在0状态时只有遇到了pat[0]才能转到状态1
dp[0][(int)pat[0]] = 1;
//初始化影子状态初始值
int X = 0;
//构建状态转移图
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状态需要进行推进所匹配的字符不匹配时 就状态重