Cod sursa(job #2863945)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 7 martie 2022 14:00:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5;

char a[N], b[N];
int lps[N];

int main() {
  ifstream cin("strmatch.in");
  ofstream cout("strmatch.out");
  cin >> (a + 1) >> (b + 1);
  cin.close();
  int n = strlen(a + 1), m = strlen(b + 1);
  int j = 0;
  for (int i = 2; i <= n; ++i) {
    while (j > 0 && a[j + 1] != a[i])
      j = lps[j];
    if (a[j + 1] == a[i])
      ++j;
    lps[i] = j;
  }
  vector<int> sol;
  j = 0;
  for (int i = 1; i <= m; ++i) {
    while (j > 0 && a[j + 1] != b[i])
      j = lps[j];
    if (a[j + 1] == b[i])
      ++j;
    if (j == n)
      sol.push_back(i - n);
  }
  cout << sol.size() << "\n";
  sol.resize(1000);
  for (auto i: sol)
    cout << i << " ";
  cout.close();
  return 0;
}