Cod sursa(job #1677162)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 6 aprilie 2016 13:14:56
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
#include<string.h>
using namespace std;
int p=73;
int MOD1=100007;
int MOD2=100021;
char a[2000002],b[20000002],match[2000002];
int n1,n2,hasha1,hasha2,p1,p2,hashb1,hashb2,nr,i;
int main()
{
      ifstream fin("strmatch.in");
     ofstream fout("strmatch.out");
     fin.get(a,2000002,'\n');
     fin.get();
     fin.get(b,2000002,'\n');
     fin.get();
     n1=strlen(a);
     n2=strlen(b);
     p1=1;
     p2=1;
     hasha1=0;
     hasha2=0;
     for(i=0;i<n1;i++)
     {
        hasha1 = (hasha1 * p + a[i]) % MOD1;
        hasha2 = (hasha2 * p + a[i]) % MOD2;
        if (i != 0)
            {
                p1 = (p1 * p) % MOD1,
                p2 = (p2 * p) % MOD2;
            }
     }
     if (n1 > n2)
     {
        fout<<"0";
        return 0;
     }
     hashb1=0;
     hashb2=0;
     for (i = 0; i < n1; i++)
     {
        hashb1 = (hashb1 * p + b[i]) % MOD1,
        hashb2 = (hashb2 * p + b[i]) % MOD2;
    }
    if (hashb1 == hasha1 && hashb2 == hasha2)
        {
            match[0] = 1;
            nr++;
        }
    for (i = n1; i < n2; i++)
    {
        hashb1 = ((hashb1 - (b[i - n1] * p1) % MOD1 + MOD1) * p + b[i]) % MOD1;
        hashb2 = ((hashb2 - (b[i - n1] * p2) % MOD2 + MOD2) * p + b[i]) % MOD2;

        if (hashb1 == hasha1 && hashb2 == hasha2)
            {
                 match[ i - n1 + 1 ] = 1;
                 nr++;
            }
    }
    fout<<nr<<'\n';
    nr = 0;
    for (i = 0; i < n2 && nr < 1000; i++)
        {
            if (match[i])
            {   nr++,
                fout<<i;
            }
        }
        fout<<'\n';

    return 0;
}