Cod sursa(job #2748398)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 30 aprilie 2021 14:13:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <string>

const int NMAX = 1e6;
const int MAX_AP = 1e3;

std::string a, b;

int pi[1 + 2 * NMAX];

int sol_size;
int sol[1 + MAX_AP];

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

  in >> a >> b;

  const int target = a.size();
  a = "." + a + "." + b;

  int k = 0;
  pi[1] = 0;

  for (int i = 2; i < a.size(); ++i) {
    while (k > 0 && a[k + 1] != a[i])
      k = pi[k];

    if (a[k + 1] == a[i])
      ++k;

    pi[i] = k;

    if (k == target) {
      ++sol_size;

      if (sol_size <= MAX_AP)
        sol[sol_size] = i - 2 * target - 1;
    }
  }

  out << sol_size << '\n';

  for (int i = 1; i <= sol_size && i <= MAX_AP; ++i)
    out << sol[i] << ' ';
  out << '\n';

  return 0;
}