Cod sursa(job #2495226)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 18 noiembrie 2019 23:01:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000000;
const int MAXK = 1000;

char a[MAXN + 5], b[MAXN + 5];
int pi[MAXN + 5];
int afis[MAXK + 5];

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  scanf("%s", a + 1);
  scanf("%s", b + 1);

  int n = strlen(a + 1);
  int m = strlen(b + 1);
  int x = 0;

  for (int i = 2; i <= n; ++i) {
    while (x > 0 && a[x + 1] != a[i])
      x = pi[x];
    if (a[x + 1] == a[i])
      x++;
    pi[i] = x;
  }

  int k = 0;
  x = 0;
  for (int i = 1; i <= m; ++i) {
    while (x > 0 && a[x + 1] != b[i])
      x = pi[x];
    if (a[x + 1] == b[i])
      x++;
    if (x == n)
      afis[++k] = i - n;
  }
  printf("%d\n", k);
  for (int i = 1; i <= k; ++i)
    printf("%d ", afis[i]);

  return 0;
}