Cod sursa(job #1943601)

Utilizator raduzxstefanescu radu raduzx Data 28 martie 2017 18:15:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <cstring>
#define p 73
#define mod1 100007
#define mod2 100021
#define nmax 2000010

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

char a[nmax],b[nmax];
int hash1,hash2,i,j,na,nb;
int match[nmax];
int main()
{
    int p1=1,p2=1,Ahash1=0,Ahash2=0;
    f>>a;
    f>>b;
    na=strlen(a);
    nb=strlen(b);
    for(i=0;i<na;i++)
    {
        Ahash1=(Ahash1*p+a[i])%mod1;
        Ahash2=(Ahash2*p+a[i])%mod2;
        if(i)
        {
            p1*=p;
            p2*=p;
            p1%=mod1;
            p2%=mod2;
        }
    }
    if(na>nb)
        g<<"0";
    else
    {
        for(i=0;i<na;i++)
        {
            hash1=(hash1*p+b[i])%mod1;
            hash2=(hash2*p+b[i])%mod2;
        }
        int nr=0;
        if(hash1==Ahash1 and hash2==Ahash2)
        {
            nr+=1;
            match[nr]=0;
        }
        for(i=na;i<nb;i+=1)
        {
            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==Ahash1 and hash2==Ahash2)
            {
                nr+=1;
                match[nr]=i-na+1;
            }
        }
        g<<nr<<'\n';
        nr=min(nr,1000);
        for(i=1;i<=nr;i++)
            g<<match[i]<<" ";
    }
    f.close();
    g.close();
    return 0;
}