Cod sursa(job #2884777)

Utilizator NanuGrancea Alexandru Nanu Data 4 aprilie 2022 20:51:25
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <cstring>

using namespace std;

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

#define DIM 2000000
#define NMAX 1005

#define BAZA1 27
#define MOD1 10007

#define BAZA2 29
#define MOD2 666013

char a[DIM + 1], b[DIM + 1];
int lga, lgb;
int ans[DIM], k;

//algoritm de tipul fereastra glisanta;
static inline void Rubin_Karp() {
  int v1, v2, p1, p2;

  p1 = p2 = 1;
  v1 = v2 = 0;
  for(int i = 0; i < lga; i++) {      //valoarea sirului a;
    v1 = (v1 * BAZA1 + a[i]) % MOD1;  
    v2 = (v2 * BAZA2 + a[i]) % MOD2;
    if(i != 1) {
      p1 = (p1 * BAZA1) % MOD1;
      p2 = (p2 * BAZA2) % MOD2;
    }
  }

  int h1 = 0, h2 = 0;
  for(int i = 0; i < lga; i++) {
    h1 = (h1 * BAZA1 + b[i]) % MOD1;   //valoarea primei subsecvente de lga din b;
    h2 = (h2 * BAZA2 + b[i]) % MOD2;
  }

  if(v1 == h1 && v2 == h2)  //daca primele secvente sunt la fel;
    ans[++k] = 1;
  
  for(int i = lga; i < lgb; i++) {
    h1 = ((h1 - (b[i - lga] * p1) % MOD1 + MOD1) * BAZA1 + b[i]) % MOD1;
    h2 = ((h2 - (b[i - lga] * p2) % MOD2 + MOD2) * BAZA2 + b[i]) % MOD2;

    if(v1 == h1 && v2 == h2) {
      k++;
      if(k <= 1000)
        ans[k] = i - lga + 1;
    } 
  }
}

int main() {
  fin >> a >> b;

  lga = strlen(a);
  lgb = strlen(b);

  if(lga > lgb) {
    fout << 0;
    return 0;
  }

  Rubin_Karp();

  fout << k << '\n';
  int n = min(1000, k);
  for(int i = 1; i <= n; i++)
    fout << ans[i] << " ";

  return 0;
}