Cod sursa(job #2506615)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 8 decembrie 2019 15:43:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

const int MAX_N = 2000005;
const unsigned int MAX_ANS = 1000;

int n, m;

int lps[MAX_N];
char p[MAX_N], t[MAX_N];

std::vector <int> ans;

int main() {
  int curr;
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  std::cin >> (p + 1) >> (t + 1);
  n = strlen(p + 1);
  m = strlen(t + 1);
  t[0] = p[0] = '\0';
  lps[0] = lps[1] = 0;
  for (int i = 2; i <= n; ++i) {
    curr = lps[i - 1];
    while (curr > 0 && p[curr + 1] != p[i]) {
      curr = lps[curr];
    }
    if (p[i] == p[curr + 1]) {
      lps[i] = curr + 1;
    } else {
      lps[i] = 0;
    }
  }
  curr = 0;
  for (int i = 1; i <= m; ++i) {
    while (curr > 0 && p[curr + 1] != t[i]) {
      curr = lps[curr];
    }
    if (p[curr + 1] == t[i]) {
      ++curr;
    } else {
      curr = 0;
    }
    if (curr == n) {
      ans.push_back(i - curr + 1);
    }
  }
  std::cout << ans.size() << "\n";
  for (int i = 0; i < std::min(MAX_ANS, ans.size()); ++i) {
    std::cout << ans[i] - 1 << " ";
  }
  return 0;
}