Cod sursa(job #2976267)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 8 februarie 2023 19:35:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>
#define mod 100007
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
long long n,m,i,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;
    ha=0;
    for (i=1; i<=n; i++)
    {
        ha=(ha*26+a[i])%mod;
        if (i>1)
            pp=(pp*26)%mod;
    }
    hb=0;
    for (i=1; i<=n; i++)
        hb=(hb*26+b[i])%mod;
    if (ha==hb)
        l[++nr]=1;
    for (i=n+1; i<=m; i++)
    {
        hb=((hb-(b[i-n]*pp)%mod+mod)*26+b[i])%mod;
        if (ha==hb)
            l[++nr]=i-n+1;
    }
    fout<<nr<<"\n";
    for (i=1; i<=min (nr,1ll*1000); i++)
        fout<<l[i]-1<<" ";
    return 0;
}