Cod sursa(job #1739723)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 10 august 2016 00:44:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cstring>
using namespace std;
const int p=73, MOD1=100007, MOD2=100021, NMAX=2000001;
int hashs1, hashs2, p1, p2, n1, n2;
char s1[NMAX], s2[NMAX], match[NMAX];
int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    in>>s1>>s2;
    n1=strlen(s1);
    n2=strlen(s2);
    p1=p2=1;
    hashs1=hashs2=0;
    for(int i=0; i<n1; i++)
    {
        hashs1=(hashs1*p+s1[i])%MOD1;
        hashs2=(hashs2*p+s1[i])%MOD2;
        if(i!=0)
        {
            p1=(p1*p)%MOD1;
            p2=(p2*p)%MOD2;
        }
    }
    if(n1>n2)
    {
        out<<0<<'\n';
        return 0;
    }
    int hash1=0, hash2=0;
    for(int i=0; i<n1; i++)
    {
        hash1=(hash1*p+s2[i])%MOD1;
        hash2=(hash2*p+s2[i])%MOD2;
    }
    int nr=0;
    if(hash1==hashs1 && hash2==hashs2)
    {
        match[0]=1;
        nr++;
    }
    for(int i=n1; i<n2; i++)
    {
        hash1=((hash1-(s2[i-n1]*p1)%MOD1+MOD1)*p+s2[i])%MOD1;
        hash2=((hash2-(s2[i-n1]*p2)%MOD2+MOD2)*p+s2[i])%MOD2;
        if(hash1==hashs1 && hash2==hashs2)
        {
            match[i-n1+1]=1;
            nr++;
        }
    }
    out<<nr<<'\n';
    nr=0;
    for(int i=0; i<n2 && nr<1000; i++)
        if(match[i])
        {
            nr++;
            out<<i<<' ';
        }
    out<<'\n';
    return 0;
}