Cod sursa(job #1492090)

Utilizator ELHoriaHoria Cretescu ELHoria Data 27 septembrie 2015 02:19:43
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

vector<int> kmp(const string& p, const string& t, const size_t& matchLimit) {
  vector<int> matches;
  vector<int> a(p.size() + 1);
  size_t j = 0;
  for (size_t i = 1; i < p.size(); i++) {
    while (p[i] != p[j] && j) j = a[j - 1];
    if (p[i] == p[j]) j++;
    a[i] = j;
  }

  for (size_t i = 0; i < t.size(); i++) {
    while (t[i] != p[j] && j) j = a[j - 1];
    if (t[i] == p[j]) j++;
    if (j == p.size()) {
      matches.push_back(i - p.size() + 1);
      j = a[j - 1];
    }
  }
  return vector<int>(matches.begin(),
      matches.begin() + min(matchLimit, matches.size()));
}

int main() {
  ifstream cin("strmatch.in");
  ofstream cout("strmatch.out");
  string a, b;
  getline(cin, a);
  getline(cin, b);
  vector<int> ans = kmp(a, b, 1000);
  cout << ans.size() << "\n";
  for (auto& x : ans) {
    cout << x << " ";
  }
}