Cod sursa(job #2589743)

Utilizator As932Stanciu Andreea As932 Data 26 martie 2020 19:57:20
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 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;
int hashN,hashM,hashS[nmax],base[nmax];

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

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

void solve()
{
    basePow();

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

    hashS[nrN-1]=hashM;
    for(int i=nrN;i<nrM;i++)
    {
        hashS[i]=(hashS[i-1]*baza+m[i])%MOD;
        hashS[i]=hashS[i]-((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-nrN+1<<" ";
    }
}

int main()
{
    read();
    solve();

    return 0;
}