Cod sursa(job #2778119)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 28 septembrie 2021 18:45:33
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long n,m,v1,v2,k1=1,k2=1,x1,x2,i,m1=1e9+7,m2=1610612741;
long long va(char c){return (c-(isupper(c)?'A':'a'-26)+1);}
char a[2000005],b[2000005];
int r[2000005],nr;
int main()
{
    fin>>a>>b;
    for(i=0;a[i];i++)
    {
        x1=((x1*53)%m1+va(a[i]))%m1;
        x2=((x2*53)%m2+va(a[i]))%m2;
        if(i>0)
        {
            k1=(k1*53)%m1;
            k2=(k2*53)%m2;
        }
    }
    n=i;
    i=0;
    for(i=0;b[i];i++)
    {
        if(i<n)
        {
            v1=((v1*53)%m1+va(b[i]))%m1;
            v2=((v2*53)%m2+va(b[i]))%m2;
            if(i==n-1&&x1==v1&&x2==v2)nr++;
        }
        else {
            v1=(v1-(va(b[i-n])*k1)%m1)%m1;
            if(v1<0)v1+=m1;
            v1=((v1*53)%m1+va(b[i]))%m1;
            v2=(v2-(va(b[i-n])*k2)%m2)%m2;
            if(v2<0)v2+=m2;
            v2=((v2*53)%m2+va(b[i]))%m2;
            if(x1==v1&&x2==v2)r[++nr]=i-n+1;
        }
    }
    fout<<nr<<'\n';
    for(i=1;i<=min(1000,nr);i++)fout<<r[i]<<' ';
    return 0;
}