Cod sursa(job #2077369)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 27 noiembrie 2017 22:38:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <string.h>

const int MAXN = 2e6;
const int MAX_POS = 1e3;

char s[MAXN + 1], p[MAXN + 1];
int pi[MAXN + 1], ans[MAX_POS];

int main() {
  int k, q, n, m;
  FILE *f = fopen("strmatch.in", "r");
  fscanf(f, "%s%s", s, p);
  fclose(f);
  k = pi[0] = 0;
  n = strlen(s);
  for (q = 1; q < n; ++q) {
    while ((k > 0) && s[q] != s[k]) {
      k = pi[k - 1];
    }
    if (s[q] == s[k]) {
      ++k;
    }
    pi[q] = k;
  }
  q = k = 0;
  m = strlen(p);
  for (int i = 0; i < m; ++i) {
    while ((q > 0) && (s[q] != p[i])) {
      q = pi[q - 1];
    }
    if (s[q] == p[i]) {
      ++q;
    }
    if (q == n) {
      if (k < MAX_POS) {
        ans[k++] = i - n + 1;
      } else {
        k++;
      }
    }
  }
  f = fopen("strmatch.out", "w");
  fprintf(f, "%d\n", k);
  k = k <= MAX_POS ? k : MAX_POS;
  for (int i = 0; i < k; ++i) {
    fprintf(f, "%d ", ans[i]);
  }
  fprintf(f, "\n");
  fclose(f);
  return 0;
}