Cod sursa(job #208228)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 14 septembrie 2008 23:55:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstring>
#include <cstdio>
#define N 2000003
char sir[N],sub[N];
long pi[N],vf;
bool poz[N];
int main ()
{FILE *fin=fopen("strmatch.in","r");
 FILE *fout=fopen("strmatch.out","w");
 fgets(sub,N,fin);
 fgets(sir,N,fin);
 memset(poz,0,sizeof(poz));
 long i,j,l1=strlen(sir),l2=strlen(sub);l2--;
 for (i=l1;i>=1;i--)
 {sir[i]=sir[i-1];}
 for (i=l2;i>=1;i--)
 {sub[i]=sub[i-1];}
 *sir=0xff;
 *sub=0xff;
// for (i=1;i<=l1;i++) {pi[i]=1;}
 
 for (j=0,i=2;i<=l2;i++)
 {while(sub[j+1]!=sub[i]&&j>0)
  {j=pi[j];
  }
  if(sub[j+1]==sub[i])
  {j++;}
  pi[i]=j;
 }
 
 for (vf=0,j=0,i=1;i<=l1;i++)
 {while(sub[j+1]!=sir[i]&&j>0)
  {j=pi[j];
  }
  if(sub[j+1]==sir[i])
  {j++;}
  if(j==l2)
  {poz[i-l2]=1;vf++;
   j=pi[j];
  }
 }
 
 fprintf(fout,"%ld\n",vf);
 for (j=1,i=0;i<=N;i++)
 {if(poz[i])
  {fprintf(fout,"%ld ",i);
   j++;
  }
  if(j==1001)break;
 }
 
 fclose (fout);
 return 0;
}