Cod sursa(job #1712373)

Utilizator dodecagondode cagon dodecagon Data 2 iunie 2016 19:21:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
//z algoritm

#include <stdio.h>
#include <string.h>


char s[4000009];
int z[4000009],n,m,p[1025],k,i;

void z_f(char *s,int * z,int n)
{
  int r=0,l=0,i,k;
  for (i=1;i<n;++i)
  {
  	if (i>r)
  	{
  		l=i;
  		r=i;
  		while (r<n && s[r-l]==s[r])
  			r++;
  		r--;

  	  z[i]=r-l+1;
  	} else 
  	{
  		if (z[i-l]<r-i+1)
  			z[i]=z[i-l]; else 
  		 {
            l=i;
  		 	while (r<n && s[r-l]==s[r])
  		 		r++;
  		 	r--;
  		 	z[i]=r-l+1;

  		 }
  	}
  }
}

int main()
{

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s",s);
    n=strlen(s);
    s[n]='#';
    scanf("%s",s+n+1);
    m=strlen(s)-n-1;

   //printf("%s \n",s);


    z_f(s,z,n+m+1);

  

  for (i=n+1;i<=n+m+1;++i)
  	if (z[i]==n)
  	{
	  	if (k<1000)
	  	  p[k]=i; 
	  	k++;
    }

    printf("%d\n",k);
    for (i=0;i<(k<1000 ? k : 1000);++i)
    	printf("%d ",p[i]-n-1);

	return 0;
}