Mai intai trebuie sa te autentifici.

Cod sursa(job #1378279)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 6 martie 2015 11:23:04
Problema Potrivirea sirurilor Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIR 2000000
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

char A[MAX_SIR];
char B[MAX_SIR];
int pi[MAX_SIR];

int raspuns[MAX_SIR];
int L = 0;

void calculare_prefix() {
  pi[0] = 0;
  int k = 0;
  int m = strlen(A), q;
  for (q = 1; q < m; q++) {
    while (k > 0 && A[k] != A[q]) {
      k = pi[k - 1];
    }
    if (A[k] == A[q]) {
      k++;
    }
    pi[q] = k;
  }
}

void KMP() {
  int q = 0, i;
  int n = strlen(B);
  int m = strlen(A);
  for (i = 0; i < n; i++) {
    while (q > 0 && A[q] != B[i]) {
      q = pi[q - 1];
    }
    if (A[q] == B[i]) {
      q++;
    }
    if (q == m) {
      raspuns[L++] = i - m + 1;
    }
  }
}

int main()
{
  FILE *in  = fopen("strmatch.in", "r");
  FILE *out = fopen("strmatch.out", "w");

  fscanf(in, "%s\n", A);
  fscanf(in, "%s\n", B);

  calculare_prefix();
  KMP();

  int i;
  fprintf(out, "%d\n", L);
  for (i = 0; i < MIN(L, 1000); i++)
    fprintf(out, "%d ", raspuns[i]);

  return 0;
}