Cod sursa(job #3256056)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 13 noiembrie 2024 09:57:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#define int long long
using namespace std;

const int B = 127, Mod = 1e9 + 7, Lmax = 2e6 + 5;

int inv[Lmax], ans[Lmax], p[Lmax];

int pow(int a, int b)
{
    if(b == 0) return 1;
    if(b == 1) return a;
    int aux = pow(a, b / 2);
    if(b % 2 == 0)
        return aux * aux % Mod;
    return ((aux * aux) % Mod) * a % Mod;
}

int invmod(int a)
{
    return pow(a, Mod - 2);
}

signed main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    int n, m, i, hasha = 0, hashb = 0, poz = 0;
    string a, b;
    cin >> a >> b;
    n = a.size(); m = b.size();
    for(i = 0; i < n; i ++) {
        p[i] = pow(B, i);
        hasha = (hasha + ((a[i] - '0' + 1) * p[i] % Mod)) % Mod;
    }
    for(int i = 0; i < n; i++) {
        hashb = (hashb + ((b[i] - '0' + 1) * p[i] % Mod)) % Mod;
    }
    if(hashb == hasha) {
        ans[++poz] = 0;
    }
    int invB = invmod(B);
    int pB = pow(B, n - 1);
    for(i = n; i < m; i++)
    {
        hashb = (hashb - (b[i - n] - '0' + 1) + Mod) % Mod;
        hashb = (hashb * invB);
        hashb = (hashb + ((b[i] - '0' + 1) * pB % Mod)) % Mod;
        if(hashb == hasha) {
            ans[++poz] = i - n + 1;
        }
    }
    cout << poz << '\n';
    for(i = 1; i <= min(poz, 1LL * 1000); i ++)
        cout << ans[i] << " ";
    return 0;
}