Cod sursa(job #3268866)

Utilizator ArseniuVictorStefanArseniu Victor Stefan ArseniuVictorStefan Data 17 ianuarie 2025 20:40:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 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;

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

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

    pi[i] = j;
  }

  vector<int> ans;

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

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

  return 0;
}