Cod sursa(job #2409648)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 19 aprilie 2019 12:30:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;

const int SQRT = 1005;
const int DIM = 2000005;

char str1[DIM], str2[DIM];
int pos[SQRT], pre[DIM];

int main(void)
{
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  cin >> (str1 + 1) >> (str2 + 1);
  int n = (int) strlen(str1 + 1),
      m = (int) strlen(str2 + 1);
  for (int i = 2, l = 0; i <= n; ++i) {
    while (l && str1[i] != str1[l + 1]) {
      l = pre[l]; }
    if (str1[i] == str1[l + 1]) {
      ++l; }
    pre[i] = l; }
  int k = 0;
  for (int i = 1, l = 0; i <= m; ++i) {
    while (l && str2[i] != str1[l + 1]) {
      l = pre[l]; }
    if (str2[i] == str1[l + 1]) {
      ++l; }
    if (l == n) {
      ++k;
      if (k <= 1000) {
        pos[k] = i - n; }
      l = pre[l]; } }
  cout << k << endl; k = min(k, 1000);
  for (int i = 1; i <= k; ++i) {
    cout << pos[i] << " "; }
  return 0;
}