Cod sursa(job #169744)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 1 aprilie 2008 22:06:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<stdio.h>
#include<string.h>
FILE*fin=fopen("strmatch.in","r");
FILE*fout=fopen("strmatch.out","w");
#define maxn 2000001
int nrp=0,n,m,p[1001],sup[maxn];
char s[maxn],t[maxn];
void prefix()
{
  int k=0,i;
  sup[1]=0;
  for(i=2;i<=m;i++)
  {
    while(k>0&&s[k]!=s[i-1]) k=sup[k];
    if(s[k]==s[i-1]) k++;
    sup[i]=k;
  }
}
void kmp()
{
  int k=0,i;
  for(i=1;i<=n;i++)
  {
    while(k>0&&s[k]!=t[i-1]) k=sup[k];
    if(s[k]==t[i-1]) k++;
    if(k==m)
    {
      nrp++;
      if(nrp<=1000) p[nrp]=i-m;
      k=sup[k];
   
    }
  }
}
int main()
{
  int i;
  fscanf(fin,"%s",&s);
  fscanf(fin,"%s",&t);
  n=strlen(t);
  m=strlen(s);
  nrp=0;
  fclose(fin);
  prefix();
  kmp();
  fprintf(fout,"%d\n",nrp);
  if(nrp>1000) nrp=1000; 
  for(i=1;i<=nrp;i++)
    fprintf(fout,"%d%c",p[i],' ');
  fclose(fout);
  return 0;
}