Cod sursa(job #2747616)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 29 aprilie 2021 14:51:56
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

const int MOD1 = 666013;
const int MOD2 = 666019;
const int BASE = 73;

const int MAX_AP = 1e3;

std::string a, b;

int cnt_ap;
int ap[1 + MAX_AP];

int main() {
  std::ifstream in("strmatch.in");
  std::ofstream out("strmatch.out");

  in >> a >> b;

  b = (char)('Z' + 1) + b;

  int hash_a1 = 0;
  int hash_a2 = 0;
  for (char i : a) {
    hash_a1 = (hash_a1 * BASE + (i - 'A')) % MOD1;
    hash_a2 = (hash_a2 * BASE + (i - 'A')) % MOD2;
  }

  int hash_b1 = 0;
  int hash_b2 = 0;
  for (int i = 0; i < a.size(); ++i) {
    hash_b1 = (hash_b1 * BASE + (b[i] - 'A')) % MOD1;
    hash_b2 = (hash_b2 * BASE + (b[i] - 'A')) % MOD2;
  }

  int power1 = 1;
  int power2 = 1;
  for (int i = 1; i < a.size(); ++i) {
    power1 = (power1 * BASE) % MOD1;
    power2 = (power2 * BASE) % MOD2;
  }

  for (int i = (int)a.size(); i < b.size(); ++i) {
    hash_b1 = ((hash_b1 - power1 * (b[i - (int)a.size()] - 'A') + MOD1) * BASE + (b[i] - 'A')) % MOD1;
    hash_b2 = ((hash_b2 - power2 * (b[i - (int)a.size()] - 'A') + MOD2) * BASE + (b[i] - 'A')) % MOD2;

    if (hash_b1 == hash_a1 && hash_b2 == hash_a2) {
      ++cnt_ap;

      if (cnt_ap <= MAX_AP)
        ap[cnt_ap] = i - (int)a.size();
    }
  }

  out << cnt_ap << '\n';
  for (int i = 1; i <= std::min(cnt_ap, MAX_AP); ++i)
    out << ap[i] << ' ';

  return 0;
}