Cod sursa(job #3208848)

Utilizator Dumiboidumitrache rares Dumiboi Data 1 martie 2024 10:57:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 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=1LL*baza*baza%mod;
           n=n/2;
       }
       else
       {
           rez=1LL*rez*baza%mod;
           n--;
       }
   }
   return rez;
}
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=0;
        nr2=0;
        nr3=0;
        nr4=0;
        for(i=0;i<n;i++)
        {

           nr1= (1LL*nr1*62+sir1[i])%mod1;
           nr2= (1LL*nr2*62+sir1[i])%mod2;
           ///al doilea sir
           nr3= (1LL*nr3*62+sir2[i])%mod1;
           nr4= (1LL*nr4*62+sir2[i])%mod2;
        }
        if(nr1==nr3 and nr2==nr4)
            cnt++,v[cnt]=0;
        int p1=putere(n-1,mod1);
        int p2=putere(n-1,mod2);
        for(i=n;i<m;i++)
        {

            nr3=((nr3-1LL*sir2[i-n]*p1%mod1+mod1)*62%mod1+sir2[i])%mod1;
            nr4=((nr4-1LL*sir2[i-n]*p2%mod2+mod2)*62%mod2+sir2[i])%mod2;

            if(nr1==nr3 and nr2==nr4)
            {
                cnt++;
                if(cnt<=1000)
                    v[cnt]=i-n+1;
            }

        }
        cout<<cnt<<"\n";
        for(i=1;i<=cnt && i<=1000;i++)
            cout<<v[i]<<" ";
    }
    return 0;
}