Cod sursa(job #3199707)

Utilizator MilitaruMihaiMihaiMIlitaru MilitaruMihai Data 2 februarie 2024 16:04:01
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define int long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod=1e9+13,p=37,p2=257;
char a[2000001],b[2000001];
int hasha[2000001],hashb[2000001],put[2000001],sol[2000001],n,k,m,k2;
int hasha2[2000001],hashb2[2000001],put2[2000001];
int32_t main()
{
   fin>>a>>b;
    n=strlen(a);
    put[0]=1;
    put2[0]=1;
    /**copiaza si asta**/
    hasha[0]=0;
    hasha2[0]=0;
    for (int i=1;i<=n;i++)
    {
        hasha[i]=hasha[i-1]*p+a[i-1];
        hasha[i]%=mod;
        put[i]=put[i-1]*p%mod;
        hasha2[i]=hasha2[i-1]*p2+a[i-1];
        hasha2[i]%=mod;
        put2[i]=put2[i-1]*p2%mod;
        //cout<<hasha[i]<<" ";
    }
    //cout<<'\n';
    hashb[0]=0;
    hashb2[0]=0;
    m=strlen(b);
     for (int i=1;i<=m;i++)
    {
        hashb[i]=hashb[i-1]*p+b[i-1];
        hashb[i]%=mod;
        hashb2[i]=hashb2[i-1]*p2+b[i-1];
        hashb2[i]%=mod;
        //cout<<hashb[i]<<" ";
    }
    //cout<<'\n';
    int nr=0;
    for (int i=0;i<m;i++)
    {
         k=((hashb[i+n-1]-hashb[i-1]*put[n])%mod+mod)%mod;
         k2=((hashb2[i+n-1]-hashb2[i-1]*put2[n])%mod+mod)%mod;
        if (k==hasha[n] && k2==hasha2[n]) nr++,sol[nr]=i-1;
    }
    fout<<nr<<'\n';
    for (int i=1;i<=nr && i<=1000;i++)
        fout<<sol[i]<<' ';
    return 0;
}