Cod sursa(job #2167025)

Utilizator amaliarebAmalia Rebegea amaliareb Data 13 martie 2018 19:51:57
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int mod1 = 666013, mod2 = 666019, MaxN = 1e6 * 2 + 5, Base = 179;
char a[MaxN], b[MaxN];

int main()
{
    f >> a >> b;
    int na = strlen(a), nb = strlen(b);
    if (nb < na) {
        g << 0 << '\n';
        return 0;
    }
    int hashA1 = 0, hashA2 = 0, hashB1 = 0, hashB2 = 0, kB1 = 1, kB2 = 1;
    for (int i = 0; i < na; ++i) {
        hashA1 = (Base * hashA1 + a[i]) % mod1;
        hashA2 = (Base * hashA2 + a[i]) % mod2;
        hashB1 = (Base * hashB1 + b[i]) % mod1;
        hashB2 = (Base * hashB2 + b[i]) % mod2;
    }
    for (int i = 1; i < na; ++i) {
        kB1 = (kB1 * Base) % mod1;
        kB2 = (kB2 * Base) % mod2;
    }
    vector<int> ans;
    int rez = 0;
    if (hashA1 == hashB1 && hashB1 == hashB2) ++rez, ans.push_back(0);
    for (int i = na; i < nb; ++i) {
        hashB1 -= (kB1 * b[i - na] - mod1) % mod1;
        hashB2 -= (kB2 * b[i - na] - mod2) % mod2;
        hashB1 = (Base * hashB1 + b[i]) % mod1;
        hashB2 = (Base * hashB2 + b[i]) % mod2;
        if (hashA1 == hashB1 && hashA2 == hashB2) {
            ++rez;
            if (rez <= 1000) ans.push_back(i - na + 1);
        }
    }
    g << rez << '\n';
    for (auto x: ans) g << x << ' ';
    return 0;
}