Cod sursa(job #2001431)

Utilizator infomaxInfomax infomax Data 16 iulie 2017 17:29:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

FILE *F=fopen("strmatch.in", "r"), *G=fopen("strmatch.out", "w");

int p1, p2, na, nb, hsh1, hsh2, hsha1, hsha2, nr;
char b[2000003], a[2000003];
bitset<2000003> mtch;
const int MOD1 = 100007;
const int MOD2 = 100021;
const int p = 73;
int main()
{
    fscanf(F, "%s %s", &a, &b);
    na = strlen(a);
    nb = strlen(b);
    if(na > nb)
    {
        fprintf(G, "%d", 0);
        return 0;
    }
    p1 = 1; p2 = 1;
    hsha1=(hsha1 * p + a[0])%MOD1,
    hsha2=(hsha2 * p + a[0])%MOD2;
    for(int i = 1; i < na; ++ i)
        hsha1=(hsha1 * p + a[i])%MOD1,
        hsha2=(hsha2 * p + a[i])%MOD2,
        p1 = p * p1,
        p2 = p * p2;
    for(int i = 0; i < na; ++ i)
        hsh1=(hsh1 * p + b[i])%MOD1,
        hsh2=(hsh2 * p + b[i])%MOD2;
    if(hsh1 == hsha1 && hsh2 == hsha2)
        nr++, mtch[0] = 1;
    for(int i = na; i < nb; ++ i)
    {
        hsh1 = ((hsh1 - (b[i-na]*p1)%MOD1 + MOD1)* p + b[i])%MOD1;
        hsh2 = ((hsh2 - (b[i-na]*p2)%MOD2 + MOD2)* p + b[i])%MOD2;

        if(hsh1 == hsha1 && hsh2 == hsha2)
            mtch[i-na+1] = 1, ++ nr;
    }
    fprintf(G, "%d\n", nr);
    nr = 0;
    for(int i = 0; i < nb && nr < 1000; ++ i)
        if(mtch[i]) ++nr, fprintf(G, "%d ", i);
    return 0;
}