给一个stream of characters(ascii)和一个hot word("a-z")，
求哪一个character可以和前面的连续字符组成这个hot word，
给出一个char, 返回true or false。
要求O(1)空间

-- Rolling hash 解法 --

// 时间是O(1)，空间是O(word.length())。
// 如果stream取样点用两个，分开word.length的距离就可以空间是O(1).

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;


int getRHash(string s) {
    int sum = 0;
    for (int i = 0; i < s.length(); ++ i) {
        sum = sum * 26 + s[i] - 'a';
    }
    return sum;
}

void check(string s, string word) {
    long long target = getRHash(word);
    int len = word.length(), weight = pow(26, len);
    cout << "target = " << target << ", len = " << len << ", weight = " << weight << endl;

    long long sum = 0;
    for (int i = 0; i < s.length(); ++ i) {
        sum = sum * 26 + s[i] - 'a';
        if (i >= len) sum -= (s[i - len] - 'a') * weight;
        if (sum == target) {
            cout << "rolling hash = " << sum << ", found match at position: " << i << endl;
        }
    }
}

int main() {
    string s = "abcebcdabcdaabcd";
    string word = "abcd";
    check(s, word);
    return 0;
}


// Output:
// target = 731, len = 4, weight = 456976
// rolling hash = 731, found match at position: 10
// rolling hash = 731, found match at position: 15

-- kmp 解法 --

Example 1:

stream = abcebcdabcd
word = abcd
-----
char  s  prefix
a     1  a
b     2  ab
c     3  abc
e     0
b     0
c     0
d     0
a     1  a
b     2  ab
c     3  abc
d     4  abcd  <-- match


Example 2:

stream = ababacd
word = abac
-----
char  s  prefix
a     1  a
b     2  ab
a     3  aba
b     2  ab
a     3  aba
c     4  abac  <-- match
d     0