Cod sursa(job #148558)

Utilizator alecmanAchim Ioan Alexandru alecman Data 4 martie 2008 15:35:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<stdio.h>
#include<string.h>

#define INPUT "strmatch.in"
#define OUTPUT "strmatch.out"

FILE *fin=fopen(INPUT,"r"),*fout=fopen(OUTPUT, "w");

char sir1[2000001],sir2[2000001];
int pref[2000001];
long vect[2001];
long cont;

void readValues();

void calculPrefix();

void KMP();

int main(){
  cont=0;
  readValues();
  calculPrefix();
  KMP();
  fclose(fin);
  fclose(fout);
  return 0;
}

void readValues(){
  char c;
  long poz=0;
  fscanf(fin, "%c", &c);
  while(c!='\n'){
    sir1[poz++]=c;
    fscanf(fin, "%c", &c);
  }
  fscanf(fin, "%c", &c);
  poz=0;
  while(c!='\n' && !feof(fin)){
    sir2[poz++]=c;
    fscanf(fin, "%c", &c);
  }
}

void calculPrefix(){
  long N;
  N=strlen(sir1);
  long k=0;
  pref[1]=0;
  for(long i=1;i<N;++i){
    while((k>0)&&(sir1[k]!=sir1[i]))
      k=pref[k];
    if(sir1[k]==sir1[i])
      ++k;
    pref[i]=k;
  }
}

void KMP(){
  long N,M;
  N=strlen(sir1);
  M=strlen(sir2);
  long q;
  q=0;
  for(long i=0;i<M;++i){
    while(q>0 && sir1[q]!=sir2[i])
      q=pref[q-1];
    if(sir1[q]==sir2[i])
      ++q;
    if(q==N){
     if(cont<1000)
     vect[++cont]=i-N;
    }
  }
  fprintf(fout, "%ld\n", cont);
  for(long i=1;i<=cont;++i)
    fprintf(fout, "%ld ", vect[i]);
  fprintf(fout, "\n");
}