Cod sursa(job #2757702)

Utilizator vlad_cvlad carasel vlad_c Data 6 iunie 2021 08:42:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int dim = 2e6+ 5;
const int baza = 29, mod = 67779;
char a[dim],b[dim];
int hasha;
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;
    for ( int i = 1;i <= n-1; ++i)
    putere = (1LL * putere * baza)%mod;
    for ( int i = 1; i <= n; ++i) {
   	 hasha = ((1LL * hasha*baza)%mod + a[i])%mod;
    }
    int hashb = 0;
    for ( int i = 1;i <= n; ++i) {
   	 hashb = ((1LL * hashb*baza)%mod + b[i])%mod;
    }
    if(hashb == hasha)
   	 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;
   	 if(hasha == hashb)
   		 sol[++cnt] = dr -n+1;
    }
    out<<cnt<<'\n';
    for(int i=1;i<=cnt && i<=1000;i++)
    {
        out<<sol[i]-1<<" ";
    }

}