Cod sursa(job #2546062)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 13 februarie 2020 19:37:02
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
char s1[2000005];
char s2[2000005];
const int mod=666013;
const int mod1=1e9+7;
const int mod2=1e9+9;
int a[100005];
int b[100005];
int c[100005];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(s1+1,2000000,stdin);fgets(s2+1,2000000,stdin);
    int n=strlen(s1+1),m=strlen(s2+1);
    --n;--m;
    long long rez=0,put=1,put1=1,put2=1,rez2=0;
    int i;
    int cnt=0;
    for(i=1;i<=n;i++)
    {
        rez=rez*27+s1[i]-'A'+1;
        rez2=rez2*27+s1[i]-'A'+1;
        if(i<n)put=put*27,put2*=27;
        put=put%mod;
        put2=put2%mod2;
        rez2%=mod2;
        rez%=mod;
    }
    long long rez1=0;
    for(i=1;i<=n;i++)
    {
        rez1=rez1*27+s1[i]-'A'+1;
        if(i<n)put1=put1*27;
        put1=put1%mod;
        rez1%=mod1;
    }
    long long calc=0,calc1=0,calc2=0;
    for(i=1;i<=n;i++)
    {
        calc=calc*27+s2[i]-'A'+1;
        calc%=mod;
        calc1=calc1*27+s2[i]-'A'+1;
        calc1%=mod1;
        calc2=calc2*27+s2[i]-'A'+1;
        calc2%=mod2;
        if(calc==rez&&calc1==rez1&&calc2==rez2)cnt++,a[cnt]=0;
    }
    for(i=n+1;i<=m;i++)
    {
        calc-=put*(s2[i-n]-'A'+1);
        calc1-=put1*(s2[i-n]-'A'+1);
        calc%=mod;
        calc1%=mod1;
        calc2-=put2*(s2[i-n]-'A'+1);
        calc2%=mod2;
        if(calc2<0)calc2+=mod2;
        if(calc<0)calc+=mod;
        if(calc1<0)calc1+=mod1;
        calc*=27;
        calc1*=27;
        calc2*=27;
        calc2+=s2[i]-'A'+1;
        calc+=s2[i]-'A'+1;
        calc1+=s2[i]-'A'+1;
        calc%=mod;
        calc1%=mod1;
        calc2%=mod2;
        if(calc==rez&&calc1==rez1&&calc2==rez2)cnt++,a[cnt]=i-1;
    }
    cout<<cnt<<"\n";
    for(i=1;i<=cnt;i++)cout<<a[i]-n+1<<" ";
    return 0;
}