Cod sursa(job #2082987)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 6 decembrie 2017 22:33:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int mod1 = 10000007;
const int mod2 = 10000021;
const int base = 131;
const int lmax = 2000005;

char s1[lmax], s2[lmax];
long long bp1, bp2, hash1, hash2, hashb1, hashb2, n, m, i, ns, sol[1005];

int main() {
    f >> (s1+1) >> (s2+1);
    n = strlen(s1+1), m = strlen(s2+1);
    if (n > m) { g << 0; return 0;}
    bp1 = bp2 = 1;
    for (i = 1; i <= n; i++) {
        hash1  = (hash1 *base+s1[i])%mod1;
        hash2  = (hash2 *base+s1[i])%mod2;
        hashb1 = (hashb1*base+s2[i])%mod1;
        hashb2 = (hashb2*base+s2[i])%mod2;

        if (i > 1)
            bp1 = (bp1*base)%mod1, bp2 = (bp2*base)%mod2;
    }
    if (hash1==hashb1 && hash2==hashb2) {
        ns++;
        if (ns <1000) sol[ns] = 0;
    }
    for (i = n+1; i <= m; i++) {
        /*hashb1 = hashb1 - (bp1*s2[i-n])%mod1;
        hashb2 = hashb2 - (bp2*s2[i-n])%mod2;*/

        hashb1 = (((hashb1 - (bp1*s2[i-n])%mod1+mod1)%mod1*base)%mod1+s2[i])%mod1;
        hashb2 = (((hashb2 - (bp2*s2[i-n])%mod2+mod2)%mod2*base)%mod2+s2[i])%mod2;

        //g << hash1 << ' ' << hashb1 << ' ' << hash2 << ' ' << hashb2 << ' ' << '\n';

        if (hash1==hashb1 && hash2==hashb2) {
            ns++;
            if (ns <1000) sol[ns] = i-n;
        }
    }

    g << ns << '\n';
    for (i = 1; i <= min(ns,1LL*1000); i++)
        g << sol[i] << ' ';
}