Cod sursa(job #2803309)

Utilizator Danut200333Dumitru Daniel Danut200333 Data 19 noiembrie 2021 19:47:00
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define baza 255
#define MOD 100007
char s[2000005], t[2000005];
int k1,k2,p1=1,p2=1,x1,x2,i,s1,s2,nr;
char sol[2000005];
int main()
{
    fin>>(s+1)>>(t+1);
    x1=strlen(s+1);
    x2=strlen(t+1);
    for(i=1; i<=x1; i++)
    {
        k1=(k1*baza+s[i])%MOD;
        k2=(k2*baza+s[i])%MOD;
        if(i!=1)
        {
            p1=(p1*baza)%MOD;
            p2=(p2*baza)%MOD;
        }
    }
    for(i=1; i<=x1; i++)
    {
        s1=(s1*baza+t[i])%MOD;
        s2=(s2*baza+t[i])%MOD;
    }
    if(s1==k1&&s2==k2)
    {
        sol[0]=1;
        nr++;
    }
    for(i=x1; i<x2; i++)
    {
        s1=((s1-(t[i-x1+1]*p1)%MOD+MOD)*baza+t[i+1])%MOD;
        s2=((s2-(t[i-x1+1]*p2)%MOD+MOD)*baza+t[i+1])%MOD;
        if(s1==k1&&s2==k2)
        {
            sol[i-x1+1]=1;
            nr++;
        }
    }
    fout<<nr<<'\n';
    for(i=1; i<=min(x2,1000); i++)if(sol[i])fout<<i<<" ";
    return 0;
}