Cod sursa(job #1956718)

Utilizator SirbuSirbu Ioan Sirbu Data 6 aprilie 2017 23:24:47
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <string.h>
#define mod1 100007
#define mod2 100021


using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

char A[2000001];
char B[2000001];
int afis[1002];

int main (){

  int P = 73;
  int P1 = 1;
  int P2 = 1;
   fin >> A >> B;
   int lgA = strlen(A);
   int lgB = strlen(B);
    // Hash pentru sirul pe care il cautam
  int hashA1 = 0;
  int hashA2 = 0;

  if (lgA > lgB){
    fout << "0\n";
    return 0;
  }

  for (int i = 0; i < lgA; ++i){
    hashA1 = (hashA1*P+A[i])%mod1;
    hashA2 = (hashA2*P+A[i])%mod2;
    // codificarea in baza P pt ambele hashuri
    if (i!=0){
      P1 = (P1*P) % mod1;
      P2 = (P2*P) % mod2;
    }
    // Puterea la care se ajunge pt cele 2 hashuri
  }

  // ABA = 26^2*A + 26*B + A

  int hashB1 = 0;
  int hashB2 = 0;
  for (int i = 0 ; i < lgA; ++i){
    hashB1 = (hashB1*P+B[i])%mod1;
    hashB2 = (hashB2*P+B[i])%mod2;
  }

  int poz = 0;
  if (hashA1 == hashB1 && hashA2 == hashB2)
    afis[++poz] = 0;

  for (int i = 1; i <= lgB - lgA; ++i){

    hashB1 = ((hashB1 - (B[i-1] * P1)%mod1 + mod1) * P + B[i+lgA-1])%mod1;
    hashB2 = ((hashB2 - (B[i-1] * P2)%mod2 + mod2) * P + B[i+lgA-1])%mod2;
    if (hashA1 == hashB1 && hashA2 == hashB2)
      afis[++poz] = i;
  }

  fout << poz << "\n";
  int cnt = 0;

  for (int i = 1; i <= poz && cnt < 1000; ++i){
    fout << afis[i] << " ";
    cnt++;
  }

}