Cod sursa(job #360867)

Utilizator proflaurianPanaete Adrian proflaurian Data 2 noiembrie 2009 15:26:28
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<string.h>
#define N 2000010
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()
{
	//se defineste functia prefix pentru surul A
	//adica pentru sirul cautat ca subsir
	for(int i=2,q=0;i<=LA;i++)
	{
		while(q&A[q+1]!=A[i])q=PA[q];
		if(A[q+1]==A[i])q++;
		PA[i]=q;
	}	
}
void potriviri()
{
	for(int i=1,q=0;i<=LB;i++)
	{
		while(q&&A[q+1]!=B[i])q=PA[q];
		if(A[q+1]==B[i])q++;
		if(q==LA){q=PA[LA];PO[++NP]=i-LA;}
	}
	printf("%d\n",NP);
	NP=NP<=1000?NP:1000;
	for(int i=1;i<=NP;i++)printf("%d ",PO[i]);
	printf("\n");	
}