Cod sursa(job #2083008)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 6 decembrie 2017 23:00:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int mod1 = 100007;
const int mod2 = 100021;
const int base = 131;
const int lmax = 2000005;

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

int main() {
    f.getline(s1+1,sizeof(s1));
    f.getline(s2+1,sizeof(s2));
    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+mod1)*base+s2[i])%mod1;
        hashb2 = (( (hashb2 - (bp2*s2[i-n]) )%mod2+mod2)*base+s2[i])%mod2;

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

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