Cod sursa(job #3268863)

Utilizator ArseniuVictorStefanArseniu Victor Stefan ArseniuVictorStefan Data 17 ianuarie 2025 20:29:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

int main()
{
  ifstream cin("strmatch.in");
  ofstream cout("strmatch.out");

  string s, t;
  cin >> s >> t;

  int n = s.size();
  s = s + "#" + t;

  vector<int> pi(s.size());
  
  pi[0] = 0;
  for (int i = 1; i < s.size(); i++) {
    pi[i] = pi[i - 1];
    while (pi[i] > 0 && s[pi[i]] != s[i]) {
      pi[i] = pi[pi[i] - 1];
    }

    if (s[pi[i]] == s[i]) {
      pi[i]++;
    }
  }

  vector<int> ans;
  ans.reserve(1000);

  for (int i = n + 1; i < s.size() && ans.size() < 1000; i++) {
    if (pi[i] == n) {
      ans.push_back(i - 2 * n);
    }
  }

  cout << ans.size() << "\n";
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";

  return 0;
}