Cod sursa(job #2589734)

Utilizator As932Stanciu Andreea As932 Data 26 martie 2020 19:35:16
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int MOD=1023317;
const int baza=29;
const int nmax=2000005;

string n,m;
int nrN,nrM;
long long hashN,hashM,hashS[nmax],base[nmax];

void citire()
{
    fin>>n>>m;
    nrN=n.length();
    nrM=m.length();
}

void basePow()
{
    base[0]=1;
    for(int i=1;i<=nrN;i++)
        base[i]=(1LL*base[i-1]*baza)%MOD;
}

void rezolvare()
{
    basePow();

    for(int i=0;i<nrN;i++)
    {
        hashN=(1LL*hashN*baza+n[i])%MOD;
        hashM=(1LL*hashM*baza+m[i])%MOD;
    }

    hashS[nrN-1]=hashM;
    for(int i=nrN;i<nrM;i++)
    {
        hashS[i]=(1LL*hashS[i-1]*baza+m[i])%MOD;
        hashS[i]=1LL*hashS[i]-((1LL*m[i-nrN]*base[nrN])%MOD);
    }

    int ans=0;
    for(int i=nrN-1;i<nrM;i++)
        if(hashS[i]==hashN)ans++;

    fout<<ans<<"\n";

    for(int i=nrN-1;i<nrM;i++)
    {
        if(hashS[i]==hashN)
            if(i<=1000)
                fout<<i-2<<" ";
    }
}

int main()
{
    citire();
    rezolvare();

    return 0;
}