Cod sursa(job #256445)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 11 februarie 2009 19:12:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <string.h>

#define IN "strmatch.in"
#define OUT "strmatch.out"
#define maxx 2000005
#define max2 2002

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

char a[maxx],b[maxx];
long v[maxx];
long poz[max2];
long sol;
long c,lung,lungg;

inline int cat(char a);
void citire();
void calc();
int verif(long i);

int main()
{
 long long i;
    
 citire();
  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])
   if(verif(i))
   {
    sol++;   
    poz[sol]=i-lungg+1; 
   }
   
  fprintf(fout,"%d\n",sol);
  
  for(i=1;i<=sol;i++)
   fprintf(fout,"%d ",poz[i]);
   
  fclose(fout);
return 0;
}

void citire()
{
 fscanf(fin,"%s %s",&a,&b);
}

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

 c=0;

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

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

 for(i=auxa;i<auxb;i++)
  v[i]=v[i-1]+cat(b[i])-cat(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;
}

inline int cat(char a)
{
 return a;
}