Cod sursa(job #519889)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 6 ianuarie 2011 19:44:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <stdio.h>
#include <string.h>

#define IN "strmatch.in"
#define OUT "strmatch.out"

#define LEN_S 2097152
#define LEN_Sol 2048

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

char a[LEN_S],b[LEN_S];
long v[LEN_S];

long poz[LEN_Sol];
long sol;

long c,lung,lungg;
int sw=1;

void calc();
int verif(long );

int main()
{
 long long i;

 fscanf(fin,"%s %s",a,b);
 fclose(fin);

 calc();

 lung=strlen(b);
 lungg=strlen(a);

 for(i=lungg-1;i<=lung-1;i++)
  if(v[i]==c && b[i]==a[lungg-1] && b[i-lungg+1]==a[0])
  {
   if(sw==1)
   {
    if(sol<=1000)
    {
     sol++;
     poz[sol]=i-lungg+1;
    }
    else
     sol++;
   }
   else
    if(verif(i)==1)
    {
     if(sol<=1000)
     {
      sol++;
      poz[sol]=i-lungg+1;
     }
     else
      sol++;
    }
  }

  fprintf(fout,"%ld\n",sol);

  for(i=1;(i<=sol && i<=1000);i++)
   fprintf(fout,"%ld ",poz[i]);

  fclose(fout);
return 0;
}

void calc()
{
 long i;
 long auxa=strlen(a);
 long auxb=strlen(b);

 c=0;

 for(i=0;i<auxa;i++)
  c=c+a[i];

 for(i=1;i<auxa;i++)
  if(a[i]!=a[0])
  {
   sw=2;
   break;
  }

 v[0]=b[0];
 for(i=1;i<auxa;i++)
  v[i]=v[i-1]+b[i];

 for(i=auxa;i<auxb;i++)
  v[i]=v[i-1]+b[i]-b[i-auxa];
}

int verif(long i)
{
 long j;
 long z=lungg-1;

 for(j=i;j>=i-lungg+1;j--)
  if(b[j]!=a[z--])
   return 0;

return 1;
}