Cod sursa(job #298370)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 6 aprilie 2009 00:06:40
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#include<string.h>
FILE*fin=fopen("kmp.in","r");
FILE*fout=fopen("kmp.out","w");
#define nm 2000005
char s[nm],t[nm];
int sup[nm],dim=0,p[nm],n,m;
void prefix()
{
  int k=0,i;
  sup[0]=0;
  for(i=1;i<m;i++)
  {
    while(k&&s[k]!=s[i]) k=sup[k-1];
    if(s[k]==s[i]) k++;
    sup[i]=k;
  }
}
void kmp()
{
  int k=0,i;
  for(i=0;i<n;i++)
  {
    while(k&&s[k]!=t[i]) k=sup[k-1];
    if(s[k]==t[i]) k++;
    if(k==m)
    {
      dim++;
      p[dim]=i-m+1;      
      k=sup[k-1];
    }
  }
}
int main()
{
  fscanf(fin,"%s",&s);
  fscanf(fin,"%s",&t);
  m=strlen(s);
  n=strlen(t);
  prefix();
  kmp();  
  fprintf(fout,"%d\n",dim);
  if(dim>1000) dim=1000;
  for(int i=1;i<=dim;i++)
    fprintf(fout,"%d ",p[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}