Cod sursa(job #154757)

Utilizator devilkindSavin Tiberiu devilkind Data 11 martie 2008 14:02:02
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define NMAX 2000002

char A[NMAX],B[NMAX];
long int pi[NMAX];
long int n,k,m,i;
int cnt;
long int sol[NMAX];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	scanf("%s",A);
	scanf("%s",B);

	n=strlen(A);
	m=strlen(B);

	k=0;
	pi[1]=0;
	
	for (i=2;i<=n;i++)
		{
			for (;k&&(A[i-1]!=A[k]);)
				k=pi[k];
			
			if (A[i-1]==A[k]) k++;
			pi[i]=k;
		}
	k=0;
	for (i=1;i<=m;i++)
		{
			for (;k&&(B[i-1]!=A[k]);) k=pi[k];

			if (B[i-1]==A[k]) k++;
			
			if (k==n)  sol[++cnt]=i-n;
		}
	printf("%ld\n",cnt);
	for (i=1;i<=min(cnt,1000);i++)
		printf("%ld ",sol[i]);
	return 0;
}