Cod sursa(job #688184)

Utilizator kis_lorikis levente lorand kis_lori Data 23 februarie 2012 09:55:41
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <string.h>

#define NMax 2000005

int n,m;
char s1[NMax],s2[NMax];
int pi[NMax], pos[1024];

void make_prefix()
{
	int i,q=0;
    pi[0]=0;
	for (i=1;i<=n;i++){
		while ((q)&&(s1[q]!=s1[i])) q = pi[q];
		if (s1[q]==s1[i]) q++;
		pi[i]=q;
	}
}

int main()
{
	int i,q=0,nr=0;
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

    scanf("%s\n%s",s1,s2); n=strlen(s1)-1; m=strlen(s2)-1;
	
	make_prefix();
 	
	for (i=0;i<=m;i++)
	{		
		while ((q)&&(s1[q]!=s2[i])) q=pi[q];
		if (s1[q] == s2[i]) q++;
		if (q==n+1){
			q=pi[n];
			nr++;
			if (nr<=1000) pos[nr]=i-n;	
		}	
	}		

	printf("%d\n", nr);
    
    if (nr>1000) nr=1000;
	for (i=1;i<=nr;i++) printf("%d ",pos[i]);
	printf("\n");

	return 0;
}