Cod sursa(job #188718)

Utilizator GagosGagos Radu Vasile Gagos Data 9 mai 2008 19:25:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
using namespace std;
#define min(a,b) ((a<b)?a:b)
#define max 2000005
int m, n;
char s1[max],s2[max];
int pi[max],pos[1024];
void make_prefix()
{
	int i,q=0;
	for(i=2,pi[1]=0;i<=m;++i){
		while(q && s1[q+1]!=s1[i])
			q=pi[q];
		if(s1[q+1]==s1[i])
			++q;
		pi[i]=q;
	}
}
int main()
{
	int i,q=0,nr=0;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(s1,sizeof(s1),stdin);
	fgets(s2,sizeof(s2),stdin);
	for(;(s1[m]>='A' && s1[m]<='Z') || (s1[m]>='a' && s1[m]<='z') || (s1[m]>='0' && s1[m]<='9'); ++m);
	for(;(s2[n]>='A' && s2[n]<='Z') || (s2[n]>='a' && s2[n]<='z') || (s2[n]>='0' && s2[n]<='9'); ++n);
	for(i=m;i;--i)
		s1[i]=s1[i-1];
	s1[0]=' ';
	for(i=n;i;--i)
		s2[i]=s2[i-1];
	s2[0]=' ';
	make_prefix();
	for(i=1;i<=n;++i){
		while(q && s1[q+1]!=s2[i])
			q=pi[q];
		if(s1[q+1]==s2[i])
			++q;
		if(q==m){
			q=pi[m];
			++nr;
			if(nr<=1000)
				pos[nr]=i-m;
		}
	}
	printf("%d\n",nr);
	for(i=1;i<=min(nr,1000);++i)
		printf("%d ",pos[i]);
	printf("\n");
	fcloseall();
	return 0;
}