Cod sursa(job #3199702)

Utilizator Lupu_Daniel_24Lupu Daniel Lupu_Daniel_24 Data 2 februarie 2024 16:00:23
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[2000005], b[2000005];
long long P1=37, mod1=1e9+13,P2=31,mod2=1e9+7;
long long sol[1001],hasha1,hasha2,hash1,hash2,hashb2[2000005],hashb1[2000005],p1[2000005],p2[2000005];
int n,m,nr;
int main()
{
    f>>a>>b;
    n=strlen(a);
    m=strlen(b);
    p1[0]=p2[0]=1;
    for(int i=1; i<m; i++)
    {
        p1[i]=(p1[i-1]*P1);
        p2[i]=(p2[i-1]*P2);
    }
    for(int i=0; i<n; i++)
    {
        hasha1=(hasha1+a[i]*p1[i]);
        hasha2=(hasha2+a[i]*p2[i]);
    }
    hashb1[0]=hashb1[0]=b[0];
    for(int i=1; i<m; i++)
    {
        hashb1[i]=(hashb1[i-1]+b[i]*p1[i]);
        hashb2[i]=(hashb2[i-1]+b[i]*p2[i]);
    }
    for(int i=0; i<=m-n; i++)
    {
        if(i==0)hash1=hashb1[i+n-1],hash2=hashb2[i+n-1];
        else hash1=(hashb1[i+n-1]-hashb1[i-1]),hash2=(hashb2[i+n-1]-hashb2[i-1]);
        if((hasha1*p1[i])==hash1 && (hasha2*p2[i])==hash2)
        {
            nr++;
            if(nr<=1000)
            {
                sol[nr]=i;
            }
        }
    }
    g<<nr<<'\n';
    for(int i=1; i<=nr; i++)
    {
        g<<sol[i]<<' ';
    }
    return 0;
}