KMP算法

class KMP{
private:
    string pat;
    vector<vector<int>> dp;
public:
    KMP(string pat){
        int M = pat.length();
        this->pat = pat;
        dp = vector<vector<int>>(M, vector<int>(256, 0));
        //base case
        dp[0][pat[0]] = 1;
        //影子状态初始化为0
        int X = 0;
        //从状态1开始
        for (int j = 1; j < M; ++j){
            for (int c = 0; c < 256; ++c){
                if (pat[j] == c)dp[j][c] = j + 1;
                else dp[j][c] = dp[X][c];
            }
            //更新影子状态
            X = dp[X][pat[j]];
        }
    }
    int search(string txt){        
        int M = pat.length();
        int N = txt.length();
        // pat 的初始态为 0
        int j = 0;
        for (int i = 0; i < N; i++) {
            // 计算 pat 的下一个状态
            j = dp[j][txt[i]];
            // 到达终止态，返回结果
            if (j == M) return i - M + 1;
        }
        // 没到达终止态，匹配失败
        return -1;        
    }
};