Cod sursa(job #504424)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 27 noiembrie 2010 17:37:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <string.h>

const int maxn=2000010;
char A[maxn],B[maxn];
int i,a,b,pi[maxn],nr,sol[1001];

void citire()
{
	A[0]=' '; scanf("%s",A+1); a=strlen(A)-1;
	B[0]=' '; scanf("%s",B+1); b=strlen(B)-1;
}

void prefixe()
{
	int k=0; pi[1]=0;
	for(i=2;i<=b;i++)
	{
		while(k>0 && A[k+1]!=A[i])
			k=pi[k];
		if(A[k+1]==A[i])
			k++;
		pi[i]=k;
	}
}

void kmp()
{
	int q=0;
	for(i=1;i<=b;i++)
	{
		while(q>0 && A[q+1]!=B[i])
			q=pi[q];
		if(A[q+1]==B[i])
			q++;
		if(q==a)
		{
			q=pi[q];
			nr++;
			if(nr<=1000) sol[nr]=i-a;
		}
	}
}

void afisare()
{
	printf("%d\n",nr);
	if(nr>1000) nr=1000;
	for(i=1;i<=nr;i++)
		printf("%d ",sol[i]);
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	citire();
	prefixe();
	kmp();
	afisare();
}