Cod sursa(job #154346)

Utilizator alecmanAchim Ioan Alexandru alecman Data 11 martie 2008 09:47:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 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[ 1001 ], 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')
  {
    if (ch >= 'A' && ch <= 'Z') ch += 32;
    sir1[ ++lg1 ] = ch;
    fscanf(fin, "%c", &ch);
  }

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

  lg2 = 0;

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

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)
    {
      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");
}