Cod sursa(job #3258201)

Utilizator GILIEDAVIDGilie David Florin GILIEDAVID Data 21 noiembrie 2024 16:00:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const long long M=1e9+13;
long long h1[2000005],h,p1=37,p[2000005],n,m,sol[1005],i,q,j,k;
string s1,s2;
int main()
{
    f>>s1>>s2;
    n=s1.size();
    m=s2.size();
    h=0;
    h1[0]=0;
    p[0]=1;
    for(i=1;i<=n;i++)
        h=(h*p1+(int)s1[i-1])%M;

    for(i=1;i<=m;i++)
    {
        h1[i]=(h1[i-1]*p1+(int)s2[i-1])%M;
        p[i]=p[i-1]*p1%M;
    }
    for(i=0;i<m-n+1;i++)
    {
        j=i+n-1;
        k=((h1[j+1]-h1[i]*p[j-i+1])%M+M)%M;
        if(k==h)
            sol[++q]=i;
    }
    g<<q<<'\n';
    if(q>1000)
        q=1000;
    for(i=1;i<=q;i++)
        g<<sol[i]<<" ";
    return 0;
}