Cod sursa(job #1201230)

Utilizator hrazvanHarsan Razvan hrazvan Data 24 iunie 2014 17:28:53
Problema Potrivirea sirurilor Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 1.13 kb
//KMP
#include <stdio.h>
#define MAXL 2000000
#define MAXOUT 1000

char A[MAXL + 1], B[MAXL + 1];
int rez[MAXL], dr = 0;
int nxt[MAXL];

int getlen(char *c){
  int rez = 0;
  while(c[rez] != '\n') rez++;
  return rez;
}

void prefix(int n){
  int i, k;
  k = -1;
  nxt[0] = -1;
  for(i = 1; i < n; i++){
    while(k > -1 && A[k + 1] != A[i]){
      k = nxt[k];
    }
    if(A[k + 1] == A[i])  k++;
    nxt[i] = k;
  }
  return ;
}

void kmp(int a, int b){
  int i, k;
  k = -1;
  for(i = 0; i < b; i++){
    while(k > -1 && A[k + 1] != B[i]){
      k = nxt[k];
    }
    if(A[k + 1] == B[i])  k++;
    if(k == a - 1){
      rez[dr] = i - a + 1;
      dr++;
    }
  }
  return ;
}

int main()
{
    FILE *in = fopen("strmatch.in", "r");
    int a, b;
    fgets(A, MAXL + 1, in);
    fgets(B, MAXL + 1, in);
    fclose(in);
    a = getlen(A);
    b = getlen(B);
    prefix(a);
    kmp(a, b);
    FILE *out = fopen("strmatch.out", "w");
    int i;
    fprintf(out, "%d\n", dr);
    for(i = 0; i < dr && i < MAXOUT; i++){
      fprintf(out, "%d ", rez[i]);
    }
    fclose(out);
    return 0;
}