// METHOD 1

// Reference: https://cp-algorithms.com/string/rabin-karp.html
//            https://cp-algorithms.com/string/string-hashing.html

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

const ll p = 31;
const ll mod = 1e9 + 7;

ll poly_rolling_hash(string s) {
    // to store the hash value of string
    ll hash = 0;

    // since p^0 = 1
    ll p_power = 1;

    for(ll i = 0; i < s.length(); i++){
        hash += (p_power * (s[i] - 'a' + 1));
        hash %= mod;
        p_power *= p;
        p_power %= mod;
    }

    return hash;
}

// fast exponentiation under modulo mod
ll fast_exponent(ll a, ll b) {
    a %= mod;
    if(a == 0) return 0;

    ll res = 1LL;

    while(b > 0){
        if(b & 1LL) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1LL;
    }

    return res;
}

// to calculate modulo multiplicative inverse of p under mudulo mod
// fermat's little theorem is used
ll mod_mul_inv(ll p) {
    return fast_exponent(p, mod - 2);
}

void rabin_karp(string text, string pat) {
    ll n = text.length();
    ll m = pat.length();

    ll text_hash = poly_rolling_hash(text.substr(0, m));
    ll pat_hash = poly_rolling_hash(pat);

    if(text_hash == pat_hash){
        cout << "Pattern starting from index: "  << 0 << "\n";
    }

    // precompute the mod_mul_inv of p under modulo mod
    ll x = mod_mul_inv(p);

    // now try to find the string in the subsequent windows of size m
    for(ll i = 1; i <= (n - m); i++){
        ll curr_hash = text_hash;

        // Step 1: remove the contribution of the first character
        // from the hash value of previous window
        curr_hash = (curr_hash - (text[i-1] - 'a' + 1) + mod) % mod;

        // Step 2: divide the hash value by p
        // as division is under modulo mod, therefore we can calculate
        // mod_mul_inv of p under modulo mod
        curr_hash *= x;
        curr_hash %= mod;

        // Step 3: inculcate the contribution of the last character of the
        // current window
        curr_hash += (fast_exponent(p, m-1) * (text[i + m - 1] - 'a' + 1));
        curr_hash %= mod;

        // compare if hashes of text and pattern comes out to be same
        if(curr_hash == pat_hash){
            cout << "Pattern starting from index: "  << i << "\n";
        }

        // update for next iteration
        text_hash = curr_hash;
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    cout << "Enter the text(haystack): ";
    string text; cin >> text; cout << text <<"\n";

    cout << "Enter the pattern to be searched(needle): ";
    string pat; cin >> pat; cout << pat <<"\n";

    if(pat.length() > text.length()){
        cout << "Pattern length > Text length" << "\n";
        return;
    }

    rabin_karp(text, pat);

    return 0;
}

/*

Sample i/p:

aabsgksaabsghaabs
aabs

Sample o/p:

Enter the text(haystack): aabsgksaabsghaabs
Enter the pattern to be searched(needle): aabs
Pattern starting from index: 0
Pattern starting from index: 7
Pattern starting from index: 13

*/

// Time complexity: O(n + m)