Cod sursa(job #2876854)

Utilizator lucriLuchian Cristian lucri Data 23 martie 2022 18:39:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 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(long long i=0;a[i];++i)
    {
        if('A'<=a[i]&&a[i]<='Z'||'0'<=a[i]&&a[i]<='9')
        {
            if('0'<=a[i]&&a[i]<='9')
                a[i]=a[i]-'0'+'A'+52;
            am1*=62;
            am1+=(long long)(a[i]-'A');
            am1%=MOD1;
            am2*=62;
            am2+=(long long)(a[i]-'A');
            am2%=MOD2;
        }
        else
        {
            am1*=62;
            am1+=(long long)(a[i]-'a'+26);
            am1%=MOD1;
            am2*=62;
            am2+=(long long)(a[i]-'a'+26);
            am2%=MOD2;
        }
    }
    pm1=pm2=1;
    for(long long i=0;a[i];++i)
    {
        pm1%=MOD1;
        pm2%=MOD2;
        if('a'<=b[i]&&b[i]<='z')
            b[i]=b[i]-'a'+'A'+26;
        else if('0'<=b[i]&&b[i]<='9')
            b[i]=b[i]-'0'+'A'+52;
        bm1*=62;
        bm1+=b[i]-'A';
        bm1%=MOD1;
        bm2*=62;
        bm2+=b[i]-'A';
        bm2%=MOD2;
        pm1*=62;
        pm2*=62;
    }
    pm1/=62;
    pm2/=62;
    if(am1==bm1&&am2==bm2)
        ans[++ans[0]]=0;
    long long l=strlen(a);
    for(long long i=l;b[i];++i)
    {
        if('a'<=b[i]&&b[i]<='z')
            b[i]=b[i]-'a'+'A'+26;
        else if('0'<=b[i]&&b[i]<='9')
            b[i]=b[i]-'0'+'A'+52;
        bm1=((bm1-(pm1*(b[i-l]-'A')%MOD1)%MOD1+MOD1)*62%MOD1+b[i]-'A'+MOD1)%MOD1;
        bm2=((bm2-(pm2*(b[i-l]-'A')%MOD2)%MOD2+MOD2)*62%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(long long i=1;i<=ans[0];++i)
        cout<<ans[i]<<' ';
    return 0;
}