Cod sursa(job #360872)

Utilizator proflaurianPanaete Adrian proflaurian Data 2 noiembrie 2009 16:35:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<stdio.h>
#include<string.h>
#define N 2000100
int LA,LB,NP,PO[N],PA[N];
char A[N],B[N],*C;
void read(),solve(),prefix(),potriviri();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	C=A;*C=' ';C++;scanf("%s",C);LA=strlen(C);
	C=B;*C=' ';C++;scanf("%s",C);LB=strlen(C);
}
void solve()
{
	prefix();
	potriviri();	
}
void prefix()
{
	int i,q=0;PA[1]=0;
	for(i=2;i<=LA;++i)
	{
		while(q>0&A[q+1]!=A[i])q=PA[q];
		if(A[q+1]==A[i])q++;
		PA[i]=q;
	}	
}
void potriviri()
{
	int i,q=0;
	for(i=1;i<=LB;++i)
	{
		while(q>0&&A[q+1]!=B[i])q=PA[q];
		if(A[q+1]==B[i])q++;
		if(q==LA){++NP;if(NP<=1000)PO[NP]=i-LA;}
	}
	printf("%d\n",NP);
	NP=NP<=1000?NP:1000;
	for(i=1;i<=NP;i++)printf("%d ",PO[i]);
	printf("\n");	
}