Cod sursa(job #278900)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 12 martie 2009 16:34:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
//BC
#include <string.h>
#include <stdio.h>
#define lg_max 2000010

char s1[lg_max],s2[lg_max] ;
int lg1,lg2,poz[lg_max];

void citire()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	fgets(s1+1,lg_max,stdin);
	lg1=strlen(s1+1);
	fgets(s2+1,lg_max,stdin);
	lg2=strlen(s2+1);
}

void pre()
{
	int k=0;
	poz[1]=0;
	for (int i=2;i<lg1;i++)
	{
		while (k && s1[k+1]!=s1[i])
			k=poz[k];
		if (s1[k+1]==s1[i])
			k++;
		poz[i]=k;
	}
}

void solve()
{
	int sol[1010];
	int cate=0;
	int k=0;

	for (int j=1;j<lg2;j++)
	{
		while (k && s1[k+1]!=s2[j])
			k=poz[k];
		if (s1[k+1]==s2[j])
			k++;
		if (k==lg1-1)
		{
			cate++;
			if (cate<1001)
				sol[cate-1]=j-lg1+1;
			k=poz[k];
		}
	}

	printf("%d\n",cate);
	if (cate>1000)
		cate=1000;
	for (int i=0;i<cate;i++)
		printf("%d ",sol[i]);
}

int main ()
{
	citire();
	pre();
	solve();
	return 0;
}