Cod sursa(job #154332)

Utilizator alecmanAchim Ioan Alexandru alecman Data 11 martie 2008 09:36:35
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<stdio.h>

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

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

long lg1, lg2;
long prefix[ NMax ], final[ NMax ], nrTotal;

char sir1[ NMax ], sir2[ NMax ];

void readValues();

void calculPrefix();

void KMP();

void printSolution();

int main()
{

  readValues();

  calculPrefix();

  KMP();

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

void readValues()
{
  char ch;

  fscanf(fin, "%c", &ch);

  lg1 = 0;

  while(ch != '\n')
  {
    sir1[ lg1++ ] = ch;
    fscanf(fin, "%c", &ch);
  }

  fscanf(fin, "%c", &ch);

  lg2 = 0;

  while(ch != '\n' && !feof( fin ) )
  {
    sir2[ lg2++ ] = ch;
    fscanf(fin, "%c", &ch);
  }
}

void calculPrefix()
{
  long poz;

  prefix[ 0 ] = 0;
  poz = 0;
  
  for( long i = 1; i < lg1; ++i)
  {

    while(poz > 0 && sir1[ poz ] != sir1[ i ])
      poz = prefix[ poz ];

    if( sir1[ poz ] == sir1[ i ] )
      ++poz;

    prefix[ i ] = poz;

  }

}

void KMP()
{
  long poz;

  poz = 0;
  nrTotal = -1;

  for( long i = 0; i < lg2; ++i)
  {

    while(poz > 0 && sir1[ poz ] != sir2[ i ] )
      poz = prefix[ poz ];

    if(sir1[ poz ] == sir2[ i ])
      ++poz;

    if(poz == lg1)
    {
      final[ ++nrTotal ] = i - lg1 + 1;
      poz = prefix[ poz - 1 ];
    }

  }

  printSolution();

}

void printSolution()
{
  fprintf(fout, "%ld\n", nrTotal + 1);

  for( long i = 0; i <= nrTotal; ++i)
    fprintf(fout, "%ld ", final[ i ]);

  fprintf(fout, "\n");
}