Cod sursa(job #3199722)

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

char a[2000005], b[2000005];
long long P=37, mod=1e9+13;
long long sol[1001],hasha,hash1,hashb[2000005],p[2000005];
int n,m,nr;
int main()
{
    f>>a>>b;
    n=strlen(a);
    m=strlen(b);
    p[0]=1;
    for(int i=1; i<m; i++)
    {
        p[i]=(p[i-1]*P)%mod;
    }
    for(int i=0; i<n; i++)
    {
        hasha=(hasha+a[i]*p[i])%mod;
    }
    hashb[0]=b[0];
    for(int i=1; i<m; i++)
    {
        hashb[i]=(hashb[i-1]+b[i]*p[i])%mod;
    }
    for(int i=0; i<=m-n; i++)
    {
        if(i==0)hash1=hashb[i+n-1];
        else hash1=(hashb[i+n-1]-hashb[i-1]+mod)%mod;
        if((hasha*p[i])%mod==hash1)
        {
            nr++;
            if(nr<=1000)
            {
                sol[nr]=i;
            }
        }
    }
    g<<nr<<'\n';
    for(int i=1; i<=nr; i++)
    {
        g<<sol[i]<<' ';
    }
    return 0;
}