Cod sursa(job #1610947)

Utilizator andrei_uAndrei andrei_u Data 23 februarie 2016 20:46:29
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <cstring>
#define mod1 100007
#define mod2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


char a[200005],b[200005];
char match[200005];

int na,nb;

int hasha1, hasha2 ,p1, p2,p,i;

int main()
{
    fin.getline(a,200005);
    fin.getline(b,200005);



    p1=p2=1;

    na=strlen(a);
    nb=strlen(b);

    for(i=0; i<na; 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(na>nb)
    {
        fout<<"0";
        return 0;
    }


    int hash1=0;
    int hash2=0;

    for (i=0; i<na; i++)
    {


        hash1 = (hash1 * p + b[i]) % mod1;
        hash2 = (hash2 * p + b[i]) % mod2;

    }

    int nr=0;

    if (hash1 == hasha1 && hash2 == hasha2)
    {
        match[0]=1;
        ++nr;
    }

    for (i=na; i<nb; i++)
    {
        hash1 = ((hash1-(b[i-na] * p1) % mod1 + mod1) * p + b[i]) % mod1;
        hash2 = ((hash2-(b[i-na] * p2) % mod2 + mod2) * p + b[i]) % mod2;

        if (hash1 == hasha1 && hash2 == hasha2)
            match[i-na+1]=1, nr++;
    }

    fout<<nr<<'\n';


    nr=0;

    for(i=0; i<nb && nr<1000; i++)
        if(match[i]!=0)
            {

            fout<<i<<" ";
            nr++;
            }
    return 0;
}