Cod sursa(job #2672700)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 14 noiembrie 2020 14:42:40
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;

long long baza = 79;
long long mod = 666773;
int cnt = 0;
int poz[1001];
int  main()
{
    string A,B;
    f    >> A >> B  ;
    long long hash_A = 0,hash_B = 0;

    for ( long long i = 0; i <A.size(); ++i) {
        hash_A = ((hash_A * baza)%mod + (A[i] -'A'+1) )%mod;
}

    for ( long long i = 0; i < A.size(); ++i) {
               hash_B = ((hash_B * baza)%mod + (B[i] -'A'+1) )%mod;
    }
    if(hash_A == hash_B) {

        ++cnt;
      poz[cnt] = 0;
    }
    long long k = A.size();
    long long powbaza[200001];
  powbaza[0] = 1;
    for ( long long i = 1; i <= k; ++i){
        powbaza[i] = (powbaza[i-1] *baza)%mod;
    }
    for ( long long i = A.size(); i < B.size(); ++i) {
        hash_B = (hash_B - (((B[i-k]-'A' + 1) * powbaza[k-1]) % mod) + mod)%mod;
        hash_B = ((hash_B * baza)%mod + (B[i] -'A'+1) )%mod;
        if(hash_B == hash_A) {
            ++cnt;
            if(cnt <= 1000)
        poz[cnt] = i-k+1;
        }
    }

    g << cnt << "\n";
    for ( int i= 1; i <= min(cnt,1000); ++i)
          g << poz[i] << " ";
    return 0;
}