Cod sursa(job #2876840)

Utilizator lucriLuchian Cristian lucri Data 23 martie 2022 18:12:03
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>
#define MOD1 1000000007
#define MOD2 1000000009
std::ifstream cin("strmatch.in");
std::ofstream cout("strmatch.out");
char a[2000010],b[2000010];
long long ans[1010],am1,am2,bm1,bm2,pm1,pm2,l1,l2;
int main()
{
    cin>>a>>b;
    if(strlen(a)>strlen(b))
    {
        cout<<0;
        return 0;
    }
    for(int i=0;a[i];++i)
    {
        if('a'<=a[i]&&a[i]<='z')
        {
            am1*=52;
            am1+=a[i]-'a';
            am1%=MOD1;
            am2*=52;
            am2+=a[i]-'a';
            am2%=MOD2;
        }
        else
        {
            am1*=52;
            am1+=a[i]-'A'+26;
            am1%=MOD1;
            am2*=52;
            am2+=a[i]-'A'+26;
            am2%=MOD2;
        }
    }
    pm1=pm2=1;
    for(int i=0;a[i];++i)
    {
        pm1%=MOD1;
        pm2%=MOD2;
        if('A'<=b[i]&&b[i]<='Z')
            b[i]=b[i]-'A'+'a'+26;
        bm1*=52;
        bm1+=b[i]-'a';
        bm1%=MOD1;
        bm2*=52;
        bm2+=b[i]-'a';
        bm2%=MOD2;
        pm1*=52;
        pm2*=52;
    }
    pm1/=52;
    pm2/=52;
    if(am1==bm1&&am2==bm2)
        ans[++ans[0]]=0;
    long long l=strlen(a);
    for(int i=l;b[i];++i)
    {
        if('A'<=b[i]&&b[i]<='Z')
            b[i]=b[i]-'A'+'a'+26;
        bm1=((bm1-(pm1*(b[i-l]-'a')%MOD1)%MOD1+MOD1)*52%MOD1+b[i]-'a'+MOD1)%MOD1;
        bm2=((bm2-(pm2*(b[i-l]-'a')%MOD2)%MOD2+MOD2)*52%MOD2+b[i]-'a'+MOD2)%MOD2;
        if(am1==bm1&&am2==bm2)
        {
            ++ans[0];
            if(ans[0]<=1000)
                ans[ans[0]]=i-l+1;
        }
    }
    cout<<ans[0]<<'\n';
    ans[0]=std::min(1LL*1000,ans[0]);
    for(int i=1;i<=ans[0];++i)
        cout<<ans[i]<<' ';
    return 0;
}