Cod sursa(job #634802)

Utilizator roxana_savulescuSavulescu Roxana roxana_savulescu Data 17 noiembrie 2011 11:55:36
Problema Potrivirea sirurilor Scor 66
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
# include <fstream>
# include<string>
# include <string.h>
using namespace std;
int hash11, hash12, hash21, hash22,na,nb,p1,p2,i,nr,sol[2000001];
string a,b;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a;
    f>>b;
    p1=p2=1;
    hash11=hash12=hash21=hash22=0;
    na = a.size();
    nb = b.size();
    for (i=0; i<na; i++)
    {
        hash11=(hash11*73+a[i]) % 100021;
        hash12=(hash12*73+a[i]) % 100007;
        if (i!=0)
        {
            p1=(p1*73)%100021;
            p2=(p2*73)%100007;
        }
    }
    if (na>nb) { printf("0\n"); return 0;}
    for (i=0; i<na; i++)
    {
        hash21=(hash21*73+b[i])% 100021;
        hash22=(hash22*73+b[i])% 100007;
    }
    nr=0;
    if (hash11==hash21 && hash12==hash22)
        {sol[0]=1; nr++;}
    for (i=na; i<nb; i++)
    {
        hash21=((hash21-(b[i-na]*p1)% 100021+100021)*73+b[i])%100021;
        hash22=((hash22-(b[i-na]*p2)% 100007+100007)*73+b[i])%100007;
        if (hash11==hash21 && hash12==hash22) {sol[i-na+1]=1; nr++;}
    }
    g<<nr<<"\n";
	nr=0;
    for (i=0; i<nb && nr<1000; i++)
        if (sol[i])
        {
            nr++;
        g<<i<<" ";
        }
    g<<"\n";
    return 0;
}