Cod sursa(job #3204337)

Utilizator Dumiboidumitrache rares Dumiboi Data 16 februarie 2024 12:08:53
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char sir1[2000001],sir2[2000001];
int v[2000001];
int mod1=666013,mod2=1000003;
int putere(int n,int mod)
{
   int rez=1,baza=62;
   while(n!=0)
   {
       if(n%2==0)
       {
           baza=1ULL*baza*baza%mod;
           n=n/2;
       }
       else
       {
           rez=1ULL*rez*baza%mod;
           n--;
       }
   }
   return rez%mod;
}
int main()
{
    cin>>sir1>>sir2;
    int n=strlen(sir1),m=strlen(sir2),i,nr1,nr2,nr3,nr4,cnt=0;
    if(n>m)
        cout<<0;
    else
    {
        nr1=(sir1[0]*62%mod1+sir1[1]%mod1)%mod1;
        nr2=(sir2[0]*62%mod2+sir2[1]%mod2)%mod2;
        nr3=(sir1[0]*62%mod2+sir1[1]%mod2)%mod2;
        nr4=(sir2[0]*62%mod1+sir2[1]%mod1)%mod1;
        for(i=2;i<n;i++)
        {
           char x=sir1[i],y=sir2[i];
           nr1+=(nr1*62%mod1+x%mod1)%mod1;
           nr2+=(nr2*62%mod2+y%mod2)%mod2;
           nr3+=(nr3*62%mod2+x%mod2)%mod2;
           nr4+=(nr4*62%mod1+y%mod1)%mod1;
        }
        if(nr1==nr4 and nr2==nr3)
            cnt++,v[cnt]=0;
        for(i=n;i<m;i++)
        {
            nr2=(((nr2-(1LL*sir2[i-n]*putere(n-1,mod2)%mod2)+mod2)*62)%mod2+sir2[i])%mod2;
            nr4=(((nr4-(1LL*sir2[i-n]*putere(n-1,mod1)%mod1)+mod1)*62)%mod1+sir2[i])%mod1;
            if(nr1==nr4 and nr2==nr3)
                cnt++,v[cnt]=i;
        }
        cout<<cnt<<"\n";
        for(i=1;i<=cnt;i++)
            cout<<v[i]<<" ";
    }

    return 0;
}