Cod sursa(job #154372)

Utilizator alecmanAchim Ioan Alexandru alecman Data 11 martie 2008 10:03:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include<stdio.h>
#include<string.h>

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

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

long lg1, lg2;
long prefix[ NMax ], final[ 1005 ], 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()
{
  fgets(sir1,sizeof(sir1),fin);

  fgets(sir2,sizeof(sir2),fin);  

  lg1 = 0;

  for(long i = strlen(sir1) - 1; i >= 0; --i)
    if(( sir1[ i ] >= 'A' && sir1[ i ] <='Z') || (sir1[ i ] >= 'a' && sir1[ i ] <='z') || (sir1[ i ] >= '0' && sir1[ i ] <= '9') ){
      sir1[ i + 1 ] = sir1[ i ];
      if( lg1 < i )
        lg1 = i+1;
    }
  sir1[0] = ' ';

  lg2 = 0;

  for(long i = strlen(sir2) - 1; i >= 0; --i)
    if(( sir2[ i ] >= 'A' && sir2[ i ] <='Z') || (sir2[ i ] >= 'a' && sir2[ i ] <='z') || (sir2[ i ] >= '0' && sir2[ i ] <= '9') ){
      sir2[ i + 1 ] = sir2[ i ];
      if( lg2 < i )
        lg2 = i+1;
    }
  sir2[0] = ' ';

}

void calculPrefix()
{
  long poz;

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

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

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

    prefix[ i ] = poz;

  }

}

void KMP()
{
  long poz;

  poz = 0;
  nrTotal = 0;

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

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

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

    if(poz == lg1)
    {
      ++nrTotal;

      if(nrTotal <= 1000)	    
        final[ nrTotal ] = i - lg1;

      poz = prefix[ poz ];
    }

  }

  printSolution();

}

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

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

  fprintf(fout, "\n");
}