Cod sursa(job #1472776)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 17 august 2015 18:25:14
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
/* 
* Z[i] = lungimea celui mai lungi subsecvente incepand cu B[i] 
* care este si prefix al lui A
*/
#include <stdio.h>
#include <string.h>

#define MAX_LEN 2000000
#define MAX_POS 1000

char A[2 * MAX_LEN + 1];
int Z[2 * MAX_LEN];
int pos[MAX_POS];

inline int MIN(int X, int Y) {
  return X < Y ? X : Y;
}

void process(char *A, int length) {
  int l = 0, r = 0;

  for (int i = 1; i < length; i++) {
    // [l, r] este segmentul curent
    if (i <= r) { // i face parte din segmentul curent
      // Z[i - l] ar putea depasi R, dar nu stim ce e in dreapta lui R
      Z[i] = MIN(r - i + 1, Z[i - l]);
    }
    while (i + Z[i] < length && A[Z[i]] == A[i + Z[i]]) {
      Z[i]++;
    }
    if (i + Z[i] - 1 > r) {
      l = i;
      r = i + Z[i] - 1;
    }
  }
}

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

  fgets(A, MAX_LEN + 1, f);
  n = strlen(A) - 1;
  fgets(A + n + 1, MAX_LEN + 1, f);
  m = strlen(A + n) - 1;
  fclose(f);

  process(A, n + m + 1);
  i = 0;
  q = 0;
  while (i <= m && q < MAX_POS) {
    if (Z[i + n] == n) {
      pos[q++] = i - 1;
    }
    i++;
  }
  while (i <= m) {
    q += (Z[i + n] == n);
    i++;
  }
  f = fopen("strmatch.out", "w");
  fprintf(f, "%d\n", q);
  q = MIN(q, MAX_POS);
  for (int i = 0; i < q; i++) {
    fprintf(f, "%d ", pos[i]);
  }
  fclose(f);
  return 0;
}