Cod sursa(job #3312541)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 29 septembrie 2025 01:29:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> prefix_function(const string& s) {
  int n = s.size();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}

vector<int> kmp_search(const string& text, const string& pattern) {
  string combined = pattern + "#" + text;
  vector<int> pi = prefix_function(combined);
  vector<int> matches;
  int m = pattern.size();
  for (int i = m + 1; i < (int)pi.size(); i++) {
    if (pi[i] == m) {
      matches.push_back(i - 2 * m);
    }
  }
  return matches;
}

int main() {
#ifndef LOCAL
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
#endif
  string pat, txt;
  cin >> pat >> txt;
  auto matches = kmp_search(txt, pat);
  cout << matches.size() << "\n";
  for (int i = 0; i < (int)matches.size(); i++) {
    if (i) cout << " ";
    cout << matches[i];
  }
  cout << "\n";
}