Z-function, prefix-function, hash

#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long ll;
typedef long double ld;

vector<int> simple_z(string s) {
    int n = (int)s.length();
    vector<int> z(n, 0);
    for (int i = 1; i < n; ++i) {
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
    }
    return z;
}

vector<int> z_function(string s) {
    int n = (int)s.length();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        if (i + z[i] - 1 > r) {
            l = i, r = i + z[i] - 1;
        }
    }
    return z;
}

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

const ll md = 1e9 + 7;
const ll x = 141;
const int MAXN = 1e6;

ll degrees[MAXN];
ll h[MAXN];

ll get_h(int i, int j) {
    return (h[j + 1] + md - h[i] * degrees[j - i + 1] % md) % md;
}

int main() {
#ifdef SYSTEM
    freopen("In.txt", "r", stdin);
    freopen("Out.txt", "w", stdout);
#endif
    degrees[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        degrees[i] = degrees[i - 1] * x % md;
    }
    string s;
    cin >> s;
    h[0] = 0;
    for (int i = 0; i < s.length(); ++i) {
        h[i + 1] = h[i] * x + s[i];
        h[i + 1] %= md;
    }
    reverse(s.begin(), s.end());
    h2...
    h[s.length()];
    return 0;
}