Cod sursa(job #1492099)

Utilizator ELHoriaHoria Cretescu ELHoria Data 27 septembrie 2015 03:01:24
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

vector<int> kmp(const string& p, const string& t) {
  vector<int> matches;
  vector<int> a(p.size());
  int 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 > 0) 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 matches;
}

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);
  cout << ans.size() << "\n";
  int k = 0;
  for (auto& x : ans) {
    cout << x << " ";
    k++;
    if (k == 1000) break;
  }
}