Cod sursa(job #3199736)

Utilizator GILIEDAVIDGilie David Florin GILIEDAVID Data 2 februarie 2024 16:22:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 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 h,hash2[2000005],p[2000005],p1=37,n,m,v[1005],k,nr,i,j,s;
string s1,s2;
int main()
{
    f>>s1>>s2;
    hash2[0]=h=0;
    p[0]=1;
    n=s1.size();
    m=s2.size();

    for(i=1;i<=n;i++)
        h=(h*p1+(int)s1[i-1])%M;
    for(i=1;i<=m;i++)
    {
        hash2[i]=(hash2[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;
        s=((hash2[j+1]-hash2[i]*p[j-i+1])%M+M)%M;
        if(s==h)
            v[++k]=i;
    }
    g<<k<<'\n';
    if(k>1000)
        k=1000;
    for(i=1;i<=k;i++)
        g<<v[i]<<" ";
    return 0;
}