Cod sursa(job #2886775)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 8 aprilie 2022 12:12:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 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());
      if (v.size() == 1000) {
        break;
      }
    }
  }
  fout << v.size() << "\n";
  for (int it : v) {
    fout << it - a.size() - 1 << " ";
  }
  return 0;
}