Cod sursa(job #410280)

Utilizator arnold23Arnold Tempfli arnold23 Data 4 martie 2010 11:16:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <string.h>

using namespace std;

const long size=2000010;
char a[size],b[size];
long pi[size],n,m,sol[1010],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) 
   {
     ++l;
     if(l<=1000) sol[l]=i-n;
     q=pi[q];
   }                  
  }  
    
  return 0;    
}

int main()
{

  ifstream in("strmatch.in");
  ofstream out("strmatch.out"); 
  
  in >> a+1;
  in >> b+1;
  a[0]=' ';
  b[0]=' ';

  n=strlen(a)-1;
  m=strlen(b)-1;

  
  prefix();
  kmp();
      
         
  out << l << endl;
  for(i=1;(i<=l && i<=1000);++i) out << sol[i] << " ";
  
  in.close();
  out.close();
   
  return 0;    
}