Cod sursa(job #2800854)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 14 noiembrie 2021 10:13:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <cstring>
#include <vector>

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[i] != a[j + 1])
      j = lps[j];
    if (a[i] == a[j + 1])
      ++j;
    lps[i] = j;
  }
  j = 0;
  vector<int> ans;
  for (int i = 1; i <= m; ++i) {
    while (j > 0 && b[i] != a[j + 1])
      j = lps[j];
    if (b[i] == a[j + 1])
      ++j;
    if (j == n)
      ans.push_back(i - j);
  }
  cout << ans.size() << "\n";
  for (int i = 0; i < min((int)ans.size(), 1000); ++i)
    cout << ans[i] << " ";
  cout.close();
  return 0;
}