Cod sursa(job #502479)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 19 noiembrie 2010 18:05:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
# include <fstream.h>
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int c[2000],n,m,i,q,p[2000005];
char a[2000005],b[2000005];

  void prefix ()
  {
	  int k=-1;
	  p[0]=k;
	  for (i=1;i<n;i++)
	  {
		  while (k>-1 && a[k+1]!=a[i])
			  k=p[k];
		  if (a[k+1]==a[i])
			  k++;
		  p[i]=k;
	  }
  }
	  

     void kmp ()
	 {
		 int k=-1;
		 for (i=0;i<m;i++)
		 {
			 while (k>-1 && a[k+1]!=b[i])
				 k=p[k];
			 
			 if (a[k+1]==b[i])
				 k++;
			 if (k+1==n)
			 {
				 q++;
				 if (q<=1000)
			     c[q]=i-n+1;
			 }
		 }
	 }

int main ()
{
	f.getline (a,2000003);
	f.getline (b,2000003);
	n=strlen (a);
	m=strlen (b);
	prefix ();
	
	kmp ();
	
	g<<q<<"\n";
	for (i=1;i<=q && i<=1000;i++)
		g<<c[i]<<" ";
return 0;
}