Cod sursa(job #2833846)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 15 ianuarie 2022 19:38:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>

const int MAX_N = 2 * 1e6;
int kmp[1 + 2 * MAX_N + 1];

int main() {
  std::ifstream fin("strmatch.in");
  std::ofstream fout("strmatch.out");
  std::string a, b;
  fin >> a >> b;
  b = a + "$" + b;
  kmp[1] = 0;
  for (int i = 2; i <= b.size(); i++) {
    int l = kmp[i - 1];
    while (b[l] != b[i - 1] && l > 0) {
      l = kmp[l];
    }
    if (b[l] == b[i - 1]) {
      kmp[i] = l + 1;
    } else {
      kmp[i] = 0;
    }
  }
  int cnt = 0;
  for (int i = 1; i <= b.size(); i++) {
    if (kmp[i] == a.size()) {
      cnt++;
    }
  }
  fout << cnt << "\n";
  for (int i = 1; i <= b.size() && cnt; i++) {
    if (kmp[i] == a.size()) {
      fout << i - 2 * a.size() - 1 << " ";
      cnt--;
    }
  }
  return 0;
}