Cod sursa(job #401223)

Utilizator arnold23Arnold Tempfli arnold23 Data 22 februarie 2010 17:44:00
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>

const long size=2000010;
char a[size],b[size];
long pi[size],n,m,sol[size],l,q,i;


int prefix()
{
    
  q=0;  
  pi[1]=0;
  for(i=2;i<=n;++i)
  {
    while(q && a[q+1]!=a[i]) q=pi[q];
    if(a[q+1]==a[i]) ++q;
    pi[i]=q;                
  }    
    
  return 0;    
}

int kmp()
{
  l=0;
  q=0;  
  for(i=1;i<=m;++i)
  {
   while(q && a[q+1]!=b[i]) q=pi[q];
   if(a[q+1]==b[i]) ++q;
   if(q==n) 
   {
     sol[++l]=i-n;
     q=pi[q];
   }                  
  }  
    
  return 0;    
}

int main()
{
  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
  
  gets(a); 
  gets(b);
  for(n=0;(a[n]>='a'&&a[n]<='z')||(a[n]>='A'&&a[n]<='Z')||(a[n]>='0'&&a[n]<='9');++n);
  for(m=0;(b[n]>='a'&&b[m]<='z')||(b[m]>='A'&&b[m]<='Z')||(b[m]>='0'&&b[m]<='9');++m);
  
  for(i=n;i;--i) a[i]=a[i-1]; a[0]=' ';
  for(i=m;i;--i) b[i]=b[i-1]; b[0]=' ';  
  
  prefix();
  kmp();
      
      
  printf("%ld\n",l);    
  for(i=1;i<=l;++i) printf("%ld ",sol[i]);    
    
  return 0;    
}