Cod sursa(job #2527633)

Utilizator Rares31100Popa Rares Rares31100 Data 20 ianuarie 2020 18:38:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 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;

LL cuvP,A=915358133,B=974328597;
LL 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;
}