Cod sursa(job #2747607)

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

const int MOD = 666013;
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_a = 0;
  for (char i : a)
    hash_a = (hash_a * BASE + (i - 'A')) % MOD;

  int hash_b = 0;
  for (int i = 0; i < a.size(); ++i)
    hash_b = (hash_b * BASE + (b[i] - 'A')) % MOD;

  int power = 1;
  for (int i = 1; i < a.size(); ++i)
    power = (power * BASE) % MOD;

  for (int i = (int)a.size(); i < b.size(); ++i) {
    hash_b = ((hash_b - power * (b[i - (int)a.size()] - 'A') + MOD) * BASE + (b[i] - 'A')) % MOD;

    if (hash_b == hash_a) {
      ++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;
}