Cod sursa(job #378191)

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

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

void urmatorul(char *P)
{
	int k=-1;
	URM[0]=0;
	for(int i=1;i<M;i++)
	{
		while(k>0 && 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);
	gets(P);
	gets(T);
	M=strlen(P);
	N=strlen(T);
	urmatorul(P);
	
	for(int i=0;i<N;i++)
	{
		while(x>0 && P[x+1]!=T[i])
			x=URM[x];
		if(P[x+1]==T[i])
			x++;
		if(x==M-1)
		{
			SOL[++NR]=i-M+1;
			x=URM[x];
		}
	}
	printf("%d\n",NR);
	for(int i=1;i<=NR;i++)
		printf("%d ",SOL[i]);
	return 0;
	
}