Cod sursa(job #165655)

Utilizator MciprianMMciprianM MciprianM Data 26 martie 2008 14:58:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>   
char a[2000002], b[2000002];   
int m, n, lim, r[1024], pi[2000002];   
void prefix(){   
  int i, k;   
  pi[1]=0;   
  k=0;   
  for(i=2;i<=m;++i){   
    while(k && a[i]!=a[k+1])   
      k=pi[k];   
    if(a[i]==a[k+1])   
      ++k;   
    pi[i]=k;   
  }   
}   
void match(){   
  int i, k;   
  k=0;   
  for(i=1;i<=n;++i){   
    while(k && a[k+1]!=b[i])   
      k=pi[k];   
    if(a[k+1]==b[i])   
      ++k;   
    if(k==m)   
    {   
      ++lim;   
      k=pi[k];   
      if(lim<1001)  r[lim]=i-m+1;   
    }   
  }   
}   
  
int main(){   
  int i;
  freopen("strmatch.in","r", stdin);   
  fgets(a, sizeof(a), stdin);      
  fgets(b, sizeof(b), stdin);    
  fclose(stdin);   
  for(n=0;(b[n]<='Z'&&b[n]>='A')||(b[n]<='z'&&b[n]>='a')||(b[n]<='9'&&b[n]>='0');++n);
  for(m=0;(a[m]<='Z'&&a[m]>='A')||(a[m]<='z'&&a[m]>='a')||(a[m]<='9'&&a[m]>='0');++m);
  for(i=m;i;--i)
    a[i]=a[i-1];
  a[m+1]=0;a[0]=' ';
  for(i=n;i;--i)
    b[i]=b[i-1];
  b[n+1]=0;b[0]=' ';
  prefix();   
  match();   
  freopen("strmatch.out","w",stdout);   
  printf("%d\n",lim);   
  int  min;   
  min=(1000<lim)?1001:(lim+1);   
  for(i=1;i<min;++i)   
    printf("%d ",r[i]);
  printf("\n");	
  fclose(stdout);   
  return 0;   
}