Cod sursa(job #2723487)

Utilizator Rares31100Popa Rares Rares31100 Data 14 martie 2021 11:31:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
	
#include <bits/stdc++.h>
#define ULL unsigned long long
 
using namespace std;
 
ifstream in("strmatch.in");
ofstream out("strmatch.out");
 
string cuv,sir;
int cuvSize,sirSize;
int sol[1001],t;
 
ULL cuvP,A=915358133,B=974328597;
ULL 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;
}