Cod sursa(job #2011853)

Utilizator BarbumateiBarbu Matei Barbumatei Data 17 august 2017 13:19:39
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000000

FILE *fin, *fout;
char a[MAXN+1], b[MAXN+1];
int nr, afis[1001], na, nb,
    pi[MAXN];

void precalc(){
  int j, i;
  j=0; pi[0]=0;
  for(i=1; i<na; i++){
    while(j>0 && a[j]!=a[i])
      j=pi[j-1];
    if(a[j]==a[i])
      j++;
    pi[i]=j;
  }
}

int main(){
  fin=fopen("strmatch.in", "r");
  fout=fopen("strmatch.out", "w");
  fgets(a, MAXN+1, fin);
  fgets(b, MAXN+1, fin);
  na=strlen(a)-1;//am pus -1 pt ca fgets memoreaza si '\n'
  nb=strlen(b)-1;//si strlen se opreste la '\0'
  precalc();

  int i, j=0;
  for(i=0; i<nb; i++){
    while(j>0 && a[j]!=b[i])
      j=pi[j-1];
    if(a[j]==b[i])
      j++;
    if(j==na){
      if(nr<1000)
        afis[nr++]=i-na+1;
      j=pi[j-1];
    }
  }

  fprintf(fout, "%d\n", nr);
  if(nr>1000)
    nr=1000;
  for(i=0; i<nr; i++)
    fprintf(fout, "%d ", afis[i]);
  fclose(fin);
  fclose(fout);
    return 0;
}