Cod sursa(job #389379)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 1 februarie 2010 15:51:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>
#include<string.h>
#define Nmax 2000010

char a[Nmax],b[Nmax],c;

int pi[Nmax],i,k,m,n,q,sol,poz[1010];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	scanf("%s%c%s",a+1,&c,b+1);
	
	n=strlen(a+1);
	m=strlen(b+1);
	
	for(i=2;i<=n;i++)
	{
		while( k>0 && a[k+1]!=a[i])
			k=pi[k];
		
		if(a[k+1]==a[i])
			k++;
		
		pi[i]=k;
	}
	
	for(i=1;i<=m;i++)
	{
		while(q>0 && a[q+1]!=b[i])
			q=pi[q];
		
		if(a[q+1]==b[i])
			q++;
		
		if(q==n) 
		{
			sol++;
			if(sol<=1000) poz[sol]=i-n;
		}
	}
	printf("%d\n",sol);
	if(sol>1000) sol=1000;
	
	for(i=1;i<=sol;i++)
		printf("%d ",poz[i]);
	
	return 0;
}