【LeetCode每日一题】28. 实现 strStr()

输入：haystack = "hello", needle = "ll"
输出：2

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        if (haystack.size() == needle.size() && haystack.size() == 0) return 0;
        for (int i=0; i<haystack.size(); i++) {
            int j = 0;
            int k = i;
            if (haystack[i] == needle[j]) {
                while (k < haystack.size() && j < needle.size() && haystack[k] == needle[j]) {
                    k++;
                    j++;
                }
                if (j == needle.size()) return i;
            }
        }
        return -1;
    }
};

class Solution {
public:
    vector<vector<int>> dp;

    void kmp(string& needle) {
        int m = needle.size();
        dp = vector<vector<int>>(m, vector<int>(256,0));
        int prev = 0;
        dp[0][needle[0]] = 1;
        for (int j = 1; j < m; j++) {
            for (int c = 0; c < 256; c++) {
                if (c == needle[j]) {
                    dp[j][c] = j + 1;
                } else {
                    dp[j][c] = dp[prev][c];
                }
            }
            prev = dp[prev][needle[j]];
        }
    }
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;
        kmp(needle);
        int prev = 0;
        for (int i = 0; i < n; i++) {
            prev = dp[prev][haystack[i]];
            if (prev == m) return i - m + 1;
        }

        return -1;
    }
};