Cod sursa(job #2527652)

Utilizator Rares31100Popa Rares Rares31100 Data 20 ianuarie 2020 19:06:47
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
#define LL long long

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

string cuv,sir;
int cuvSize,sirSize;
int sol[1001],t;

int cuvP,A=9130,B=9731;
int h[2000001],p[2000001];

void build()
{
    for(auto lit:cuv)
        cuvP=(cuvP*A+lit)%B;

    p[0]=1;

    for(int i=1;i<=sirSize;i++)
    {
        h[i]=(h[i-1]*A+sir[i-1])%B;
        p[i]=(p[i-1]*A)%B;
    }
}

void rabinKarp()
{
    for(int i=cuvSize;i<=sirSize;i++)
    {
        if( (h[i]-h[i-cuvSize]*p[cuvSize]+B*B)%B==cuvP )
        {
            t++;
            if(t<=1000)
                sol[t]=i-cuvSize;
        }
    }
}

int main()
{
    in>>cuv>>sir;
    cuvSize=cuv.size();
    sirSize=sir.size();

    build();
    rabinKarp();

    out<<t<<'\n';

    for(int i=1;i<=min(t,1000);i++)
        out<<sol[i]<<' ';

    return 0;
}