Cod sursa(job #2690427)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 23 decembrie 2020 22:24:11
Problema Potrivirea sirurilor Scor 40
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>

#define MAXN 2000000
#define MAX_MATCH 1000

int lps[MAXN];// AFD
char src[MAXN + 1];// search
char str[MAXN + 1];

int match[MAX_MATCH];

int strLen( char *str ){
  int i = 0;
  while( *(str + (i++)) );
  return i - 1;// scap de '\0'
}

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

  int i, j, n, m, nmatch, last;

  fgets(src, MAXN + 1, fin);
  fgets(str, MAXN + 1, fin);
  m = strLen(src);
  n = strLen(str);

  if( src[m - 1] == '\n' )
    m--;

  if( str[n - 1] == '\n' )
    n--;

  // calculam lps
  lps[0] = last = 0;
  
  i = 1;
  while( i < m ){// nu avem nr. cunoscut de pasi
    if( src[i] == src[lps[i - 1]] ){
      lps[i++] = ++last;
    }else{
      if( last > 0 )// daca inca mai putem incerca
        last = lps[last];// incercam prima valoare mai mica care ar putea sa mearga
      else// daca am esuat
        lps[i++] = 0;
    }
  }
  
  // facem KMP propriu zis
  i = j = 0;
  nmatch = 0;
  while( i < n ){// nu avamsam mereu cu o poz. putem sta pe loc cand avem missmatch
    if( src[j] == str[i] ){
      i++;
      j++;
    }else{
      if( j == 0 )
        i++;
      else
        j = lps[j - 1];
    }

    if( j == m ){// daca avem match
      match[nmatch++] = i - m;
      j = lps[j - 1];
    }
  }

  fprintf(fout, "%d\n", nmatch);
  nmatch = MAX_MATCH < nmatch ? MAX_MATCH : nmatch;
  for( i = 0 ; i < nmatch ; i++ )
    fprintf(fout, "%d ", match[i]);
  fputc('\n', fout);

  fclose(fin);
  fclose(fout);
  return 0;
}