Cod sursa(job #369056)

Utilizator cosgbCosmin cosgb Data 26 noiembrie 2009 22:39:01
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <string.h>


long nr=0,sol[1002];

void preKMP (char *x,int m,int KMPshift[])
{ int i,j;
i=0;
j=KMPshift[0]=-1;
while (i<m)
{ while (j>-1&&x[i]!=x[j])
	                 j=KMPshift[j];
    ++i;
	++j;
	if (x[i]==x[j])
		      KMPshift[i]=KMPshift[j];
	else
		KMPshift[i]=j;
}
}



void KMP (char *x,char *y,int n,int m)
{ int i,j;
int KMPshift[2000000];
preKMP (y,m,KMPshift);
i=j=0;
while (i<=n)
       {
		   while ((j>-1)&&(x[i]!=y[j]))
			               j=KMPshift[j];
		   ++i;++j;
		   if (j>=m)
		        {nr++;
					sol[nr]=i-j;
		         j=KMPshift[j];
				}
       }
}



int main ()
{ freopen ("strmatch.in","r",stdin);
  freopen ("strmatch.out","w",stdout);
  char x[2000000];
  char y[2000000];
  long n,m,i;
  gets(y);
  gets(x);
  n=strlen (x);
  m=strlen (y);
  KMP (x,y,n,m);
  printf ("%ld\n",nr); 
  if (nr<=1000)
  for (i=1;i<=nr;i++)
	  printf ("%ld ",sol[i]);
       else
		     for (i=1;i<=1000;i++)
				 printf ("%ld ",sol[i]);
  return 0;
}