Cod sursa(job #1712422)

Utilizator dodecagondode cagon dodecagon Data 2 iunie 2016 20:40:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
//kmp algorithm

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

char p[2000009],txt[2000009];
int f[2000009],n,m,i,k,j,sol[1024];

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

int main()
{

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

  scanf("%s",p);
  scanf("%s",txt);
  n=strlen(p);
  m=strlen(txt);

  getphi();

  
  
   k=0;
   j=0;
    
    for (i=0;i<m;++i)
    {
       while (j>0 && p[j]!=txt[i])
       	  j=f[j-1];
       	if (txt[i]==p[j])
       		j++;
       	if (j==n)
       	{
       		if (k<1000)
       			sol[k]=i-n+1;
       		k++;
       	}
       
    }

    printf("%d\n",k);

    for (i=0;i<(k<1000 ? k : 1000);++i)
    	printf("%d ",sol[i]);
    	
 
	return 0;
}