Cod sursa(job #667739)

Utilizator mavroMavrodin Bogdan-Florentin mavro Data 23 ianuarie 2012 17:59:18
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <string.h>

#define MAX 2000005

char N[MAX], M[MAX];
int n, m;
int nr_ap = 0, vect_ap[1001];
int pi[MAX];

void algoritm_calcul_functie_prefix() {
   int i, k = 0;
   
   pi[1] = 0;
   for(i = 2; i <= n; i++) {
      while(k > 0 && N[k + 1] != N[i]) {
         k = pi[k];
      }
      if(N[k + 1] == N[i]) {
   	 k++;
      }
      pi[i] = k;
   }
}


void algoritm_potrivire_KMP() {
   int i, q = 0;
   for(i = 1; i <= m; i++) {
      while((q > 0) && (N[q + 1] != M[i]))
         q = pi[q];
      if(N[q + 1] == M[i])
         q++;
      if(nr_ap == 1000)
         return;
      if(q == n)
         vect_ap[nr_ap++] = i-n;
   }
}

int main() {
   
   if(freopen("strmatch.in", "r", stdin) == 0) {
      printf("!ERROR! No file found");
      return 0;
   }
   
   if(freopen("strmatch.out", "w", stdout) == 0) {
      printf("!ERROR! No file found");
      return 0;
   }
         
   if(scanf("%s\n%s", N, M) == 0) {
      printf("!ERROR! No input found in the file");
      return 0;
   }
   
   int i;
   n = strlen(N);
   m = strlen(M);
   
   for(i = n; i > 0; i--)
      N[i] = N[i-1];
   for(i = m; i > 0; i--)
      M[i] = M[i-1];
         
   algoritm_calcul_functie_prefix();
   algoritm_potrivire_KMP();
   
   printf("%d\n", nr_ap);
   
   for(i = 0; i < nr_ap; i++)
      printf("%d ", vect_ap[i]);
   
   return 0;
}