Cod sursa(job #2790567)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 29 octombrie 2021 10:53:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define m1 100007
#define m2 100021
#define p 123
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,v1,v2,k1=1,k2=1,x1,x2,i;
char a[2000005],b[2000005];
int r[1005],nr;
int main()
{
    fin>>a>>b;
    for(i=0;a[i];i++)
    {
        x1=(x1*p+a[i])%m1;
        x2=(x2*p+a[i])%m2;
        if(i>0)
        {
            k1=(k1*p)%m1;
            k2=(k2*p)%m2;
        }
    }
    n=i;
    for(i=0;b[i];i++)
    {
        if(i<n)
        {
            v1=(v1*p+b[i])%m1;
            v2=(v2*p+b[i])%m2;
            if(i==n-1&&x1==v1&&x2==v2)nr++;
        }
        else {
            v1=((v1-(b[i-n]*k1)%m1+m1)*p+b[i])%m1;
            v2=((v2-(b[i-n]*k2)%m2+m2)*p+b[i])%m2;
            if(x1==v1&&x2==v2)
            {
                if(nr<1000)
                    r[++nr]=i-n+1;
                else nr++;
            }
        }
    }
    fout<<nr<<'\n';
    if(nr>1000)nr=1000;
    for(i=1;i<=nr;i++)fout<<r[i]<<' ';
    return 0;
}