Cod sursa(job #1770647)

Utilizator thewildnathNathan Wildenberg thewildnath Data 4 octombrie 2016 18:05:42
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <string.h>

enum {
  NMAX = 2000000
};

char a[1 + NMAX + 1];
char b[1 + NMAX + 1];
int pi[1 + NMAX];

int *build_prefix(char *a, int l1, int *pi) {
  pi[1] = 0;

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

  return pi;
}

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

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

  int l1 = strlen(a + 1);
  int l2 = strlen(b + 1);

  build_prefix(a, l1, pi);

  int match_count = 0;
  int solutions[1001];

  int pos = 0;
  for (int i = 1; i <= l2; ++i) {
    while (pos > 0 && a[pos + 1] != b[i])
      pos = pi[pos];
    if (a[pos + 1] == b[i])
      ++pos;
    if (pos == l1) {
      ++match_count;
      if (match_count <= 1000)
        solutions[match_count] = i;
    }
  }

  printf("%d\n", match_count);
  for (int i = 1; i <= match_count && i <= 1000; ++i)
    printf("%d ", solutions[i] - l1);
  printf("\n");

  return 0;
}