Cod sursa(job #378222)

Utilizator ooctavTuchila Octavian ooctav Data 27 decembrie 2009 22:42:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <cstring>
#define NMAX 2000002
#define MMAX 2000001

int URM[MMAX];
char T[NMAX],P[1024];
int SOL[NMAX],NR=0;
int N=0,M=0;

void urmatorul(char *P)
{
	int k=0;
	URM[1]=0;
	for(int i=2;i<=M;i++)
	{
		while(k && P[k+1]!=P[i])
			k=URM[k];
		if(P[k+1]==P[i])
			k++;
		URM[i]=k;
	}
}


int main()
{
	int x=-1;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(P,MMAX,stdin);
	fgets(T,NMAX,stdin);
	for (; (P[M] >= 'A' && P[M] <= 'Z') || (P[M] >= 'a' && P[M] <= 'z') || (P[M] >= '0' && P[M] <= '9'); ++M);
	for (; (T[N] >= 'A' && T[N] <= 'Z') || (T[N] >= 'a' && T[N] <= 'z') || (T[N] >= '0' && T[N] <= '9'); ++N);
	for (int i = M; i; --i) 
		P[i] = P[i-1]; P[0] = ' ';
	for (int i = N; i; --i) 
		T[i] = T[i-1]; T[0] = ' ';
	
	urmatorul(P);
	
	for(int i=1;i<=N;i++)
	{
		while(x && P[x+1]!=T[i])
			x=URM[x];
		if(P[x+1]==T[i])
			x++;
		if(x==M)
		{
			if(NR<1000)
				SOL[++NR]=i-M;
			x=URM[x];
		}
	}
	
	printf("%d\n",NR<1000?NR:1000);
	for(int i=1;i<=(NR<1000?NR:1000);i++)
		printf("%d ",SOL[i]);
	return 0;
	
}