28. Implement strStr()

rolling hash O(h + n)
hash = (hash * base + ord(c)) % modulus
modulus 必须是一个大质数（比 ord(c)要大，否则 C++会算出负数，Python 不会）来避免过多的 collision
必须要解决 hash collision，反例
“gytisyz”
“aaaaaab”

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        h, n = len(haystack), len(needle)
        if h < n: return -1
        highest_power, hh, nh = 1, 0, 0
        M, B = 2**31 - 1, 256
        for i in range(n):
            highest_power = (highest_power * B) % M
            hh = (hh * B + ord(haystack[i])) % M
            nh = (nh * B + ord(needle[i])) % M
        for i in range(h - n + 1):
            if i >= 1:
                hh = (hh * B + M - ord(haystack[i - 1]) * highest_power % M + ord(haystack[i + n - 1])) % M
            if hh == nh:
                for j in range(n):
                    if haystack[i + j] != needle[j]:
                        break
                else:
                    return i
        return -1

class Solution {
public:
    int strStr(string haystack, string needle) {
        int h = haystack.length(), n = needle.length();
        long M = INT_MAX, B = 256;
        if (h < n) return -1;
        long highest_power = 1, hh = 0, nh = 0;
        for (int i = 0; i < n; ++i) {
            highest_power = (highest_power * B) % M;
            nh = (nh * B + needle[i]) % M;
            hh = (hh * B + haystack[i]) % M;
        }
        for (int i = 0; i <= h - n; ++i) {
            if (i >= 1) {
                hh = (hh * B + M - haystack[i - 1] * highest_power % M + haystack[i + n - 1]) % M; // 这里highest_power是B的n次方，因为先整体左移再减高位，如果先减高位再整体左移就是n-1次方了
            }
            if (hh == nh && haystack.substr(i, n) == needle) {
                return i;
            }
        }
        return -1;
    }
};

class Solution {
public:
    int strStr(string haystack, string needle) {
        int h = haystack.length(), n = needle.length();
        long M = INT_MAX, B = 256; // INT_MAX是质数！
        if (h < n) return -1;
        long highest_power = 1, hh = 0, nh = 0;
        for (int i = 0; i < n; ++i) {
            highest_power = (highest_power * B) % M;
            nh = (nh * B + needle[i]) % M;
            hh = (hh * B + haystack[i]) % M;
        }
        for (int i = 0; i <= h - n; ++i) {
            if (i >= 1) {
                hh = (hh * B + M - haystack[i - 1] * highest_power % M + haystack[i + n - 1]) % M; // 这里highest_power是B的n次方，因为先整体左移再减高位，如果先减高位再整体左移就是n-1次方了
            }
            if (hh == nh) {
                int j = 0;
                for (; j < n; ++j) {
                    if (haystack[i + j] != needle[j]) break;
                }
                if (j == n) return i;
            }
        }
        return -1;
    }
};

O(nh)

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not haystack and not needle:
            return 0
        h, n = len(haystack), len(needle)
        for i in range(h - n + 1):
            if haystack[i:i + n] == needle:
                return i
        return -1

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = needle.length(), h = haystack.length();
        for (int i = 0; i <= h - n; ++i) {
            if (haystack.substr(i, size(needle)) == needle) return i;
        }
        return -1;
    }
};

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = needle.length(), h = haystack.length();
        for (int i = 0; i <= h - n; ++i) {
            int j = 0;
            for (; j < n; ++j) {
                if (haystack[i + j] != needle[j]) break;
            }
            if (j == n) return i;
        }
        return -1;
    }
};