String Hashing

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 100;
const int64_t mod = 1e9 + 7;
const int64_t p = 31;
int64_t inv[maxN],pref[maxN];

int64_t get_power (int64_t a,int64_t n) {
    int64_t res = 1;
    while (n) {
        if (n & 1) res = (res * a) % mod;
        n >>= 1;
        a = (a * a) % mod;
    }
    return res;
}

void init(string s) {
    int64_t power = 1;
    inv[0] = 1;
    pref[0] = s[0] - 'a' + 1;
    for (int i = 1; i < (int) s.size(); ++i) {
        power *= p;
        power %= mod;
        inv[i] = get_power(power,mod - 2);
        pref[i] = (pref[i - 1] + (s[i] - 'a' + 1) * power) % mod;
    }
}

int64_t Hash (int l,int r) {
    int64_t res = pref[r];
    if (l > 0) res = (res - pref[l - 1] + mod) % mod;
    res = (res * inv[l]) % mod;
    return res;
}

int64_t single_Hash (string s) {
    int64_t res = 0;
    int64_t power = 1;
    for (int i = 0; i < (int) s.size(); ++i) {
        res = (res + (s[i] - 'a' + 1) * power) % mod;
        power = (power * p) % mod;
    }
    return res;
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     //~ freopen ("input.txt", "r", stdin);
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n;
         while (cin >> n and EOF) {
             string s,t;
             cin >> t >> s;
             init(s);
             int64_t single = single_Hash(t);
             bool no = true;
             for (int i = n - 1; i < (int) s.size(); ++i) {
                 if (single == Hash(i - n + 1,i)) {
                     cout << i - n + 1 << "\n";
                     no = false;
                 }
             }
             if (no) cout << "\n";
         }
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}