Cod sursa(job #2886777)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 8 aprilie 2022 12:14:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <vector>

const int MAX_N = 2 * 1e6;
int kmp[1 + 2 * MAX_N];
std::vector<int> v;

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 (l > 0 && b[i - 1] != b[l]) {
      l = kmp[l];
    }
    if (b[i - 1] != b[l]) {
      kmp[i] = 0;
    } else {
      kmp[i] = l + 1;
    }
  }
  for (int i = 1; i <= b.size(); i++) {
    if (kmp[i] == a.size()) {
      v.push_back(i - a.size());
    }
  }
  fout << v.size() << "\n";
  int cnt = std::min((int)v.size(), 1000);
  for (int it : v) {
    fout << it - a.size() - 1 << " ";
    cnt--;
    if (cnt == 0) {
      return 0;
    }
  }
  return 0;
}