Cod sursa(job #1770609)

Utilizator thewildnathNathan Wildenberg thewildnath Data 4 octombrie 2016 17:39:48
Problema Potrivirea sirurilor Scor 4
Compilator c Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>
#include <string.h>

enum {
  NMAX = 2000000
};

char a[NMAX];
char b[NMAX];
int kmp[NMAX];

int *build_kmp(char *a, char *b, int l1, int l2, int *kmp) {
  memset(kmp, 0, sizeof(kmp));

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

  return kmp;
}

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_kmp(a, b, l1, l2, kmp);

  int match_count = 0;
  int solutions[1001];

  for (int i = 1; i <= l2; ++i)
    if (kmp[i] == l1)
      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;
}