// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem28.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=28 lang=cpp
 *
 * [28] 实现 strStr()
 */

// @lc code=start
class Solution {
private:
    vector<vector<int> > dp;

public:
    void KMP(string& pat) {
        int m = pat.size();
        for (int i = 0; i < m + 1; ++i) {
            dp.emplace_back(vector<int>(256));
        }
        dp[0][pat[0]] = 1;
        int X = 0;
        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < 256; ++j) {
                dp[i][j] = dp[X][j];
            }
            dp[i][pat[i]] = i + 1;
            X = dp[X][pat[i]];
        }
    }

    int strStr(string haystack, string needle) {
        KMP(needle);
        int n = haystack.size();
        int m = needle.size();
        int j = 0;
        for (int i = 0; i < n; ++i) {
            j = dp[j][haystack[i]];
            if (j == m) return i - m + 1;
        }
        return -1;
    }
};
// @lc code=end