Cod sursa(job #2976482)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 9 februarie 2023 11:31:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <cstring>
#define mod 100007
#define mod1 100021
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
long long n,m,i,pp1,haa,hbb,pp,ha,hb,nr,l[2000001];
char a[2000001],b[2000001];
int main()
{
    fin>>a+1;
    fin>>b+1;
    n=strlen (a+1);
    m=strlen (b+1);
    if (n>m)
    {
        fout<<"0";
        return 0;
    }
    pp=1;
    pp1=1;
    ha=0;
    haa=0;
    for (i=1; i<=n; i++)
    {
        ha=(ha*26+a[i])%mod;
        haa=(haa*26+a[i])%mod1;
        if (i>1)
        {
            pp=(pp*26)%mod;
            pp1=(pp1*26)%mod1;
        }
    }
    hb=0;
    hbb=0;
    for (i=1; i<=n; i++)
    {
        hb=(hb*26+b[i])%mod;
        hbb=(hbb*26+b[i])%mod1;
    }
    if (ha==hb&&haa==hbb)
        l[++nr]=1;
    for (i=n+1; i<=m; i++)
    {
        hb=((hb-(b[i-n]*pp)%mod+mod)*26+b[i])%mod;
        hbb=((hbb-(b[i-n]*pp1)%mod1+mod1)*26+b[i])%mod1;
        if (ha==hb&&haa==hbb)
            l[++nr]=i-n+1;
    }
    fout<<nr<<"\n";
    for (i=1; i<=min (nr,1ll*1000); i++)
        fout<<l[i]-1<<" ";
    return 0;
}