Cod sursa(job #1472986)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 18 august 2015 12:08:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <string.h>

#define MAX_LEN 2000000
#define MAX_POS 1000

int pos[MAX_POS];
char a[MAX_LEN + 2];
char b[MAX_LEN + 2];
int pi[MAX_LEN]; // pi[i] = lungimea celui mai lung prefix al S[1..i]
                 // care este si sufix al S[1..i]

void buildPrefix(char *s, int length) {
  int q = 0;

  pi[0] = 0;
  for (int i = 1; i < length; i++) {
    while ((q > 0) && (s[i] != s[q])) {
      q = pi[q - 1];
    }
    if (s[q] == s[i]) {
      q++;
    }
    pi[i] = q;
  }
}

int main(void) {
  int n, m;
  int q;
  int ans;
  FILE *f = fopen("strmatch.in", "r");

  fgets(a, MAX_LEN + 2, f);
  fgets(b, MAX_LEN + 2, f);
  fclose(f);

  n = strlen(a) - 1;
  m = strlen(b) - 1;

  buildPrefix(a, n);
  q = 0;
  ans = 0;
  for (int i = 0; i < m; i++) {
    while ((q > 0) && (a[q] != b[i])) {
      q = pi[q - 1];
    }
    if (a[q] == b[i]) {
      q++;
    }
    if (q == n) {
      if (ans < MAX_POS) {
        pos[ans] = i;
      }
      ans++;
    }
  }
  f = fopen("strmatch.out", "w");
  fprintf(f, "%d\n", ans);
  if (ans > MAX_POS) {
    ans = MAX_POS;
  }
  for (int i = 0; i < ans; i++) {
    fprintf(f, "%d ", pos[i] - n + 1);
  }
  fclose(f);
  return 0;
}