Cod sursa(job #2757704)

Utilizator vlad_cvlad carasel vlad_c Data 6 iunie 2021 08:53:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int dim = 2e6+ 5;
const int baza = 73, mod = 100021,baza2=73,mod2=100007;
char a[dim],b[dim];
int hasha,hasha2;
int sol[dim];
int cnt= 0;
int main() {

    in >> (a+1) >> (b+1);
    int n = strlen(a+1);
    int m = strlen(b+1);
    int putere = 1,putere2=1;
    for ( int i = 1;i <= n-1; ++i){
       putere = (1LL * putere * baza)%mod;
       putere2=(1LL * putere2 * baza2)%mod2;
    }
    for ( int i = 1; i <= n; ++i) {
   	 hasha = ((1LL * hasha*baza)%mod + a[i])%mod;
   	 hasha2 = ((1LL * hasha2*baza2)%mod2 + a[i])%mod2;
    }
    int hashb = 0,hashb2=0;
    for ( int i = 1;i <= n; ++i) {
   	 hashb = ((1LL * hashb*baza)%mod + b[i])%mod;
   	 hashb2 = ((1LL * hashb2*baza2)%mod2 + b[i])%mod2;
    }
    if((hashb == hasha) && (hashb2==hasha2))
   	 sol[++cnt] = 1;
    for ( int dr = n+1; dr <= m; ++dr) {
   	 hashb = (hashb - ((1LL * b[dr- n] * putere))%mod + mod)%mod;
   	 hashb = ((1LL * hashb*baza))%mod;
   	 hashb = (hashb + b[dr])%mod;
   	 hashb2 = (hashb2 - ((1LL * b[dr- n] * putere2))%mod2 + mod2)%mod2;
   	 hashb2 = ((1LL * hashb2*baza2))%mod2;
   	 hashb2 = (hashb2 + b[dr])%mod2;
   	 if((hasha == hashb) && (hasha2==hashb2))
   		 sol[++cnt] = dr -n+1;
    }
    out<<cnt<<'\n';
    for(int i=1;i<=cnt && i<=1000;i++)
    {
        out<<sol[i]-1<<" ";
    }

}