Cod sursa(job #170069)

Utilizator vlad_olteanVladimir Oltean vlad_oltean Data 2 aprilie 2008 13:07:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define N 2000010

char a[N],b[N];
int pi[N];
int sol[1001],count=0;

void citeste()
{
	freopen("strmatch.in","r",stdin);
	scanf("%s\n",a+1);
	scanf("%s",b+1);
	fclose(stdin);
}

void scrie()
{
	freopen("strmatch.out","w",stdout);
	printf("%d\n",count);
	for(int i=1;i<=count;i++) printf("%d ",sol[i]);
	fclose(stdout);
}

void rezolva()
{   int i;
	int n=strlen(a+1),m=strlen(b+1);
	int k=0;
	//pi=(int*)malloc((n+1)*sizeof(int));
	pi[1]=0;
	for(i=2;i<=n;i++)
	{	while(k&&a[i]!=a[k+1]) k=pi[k];
		if(a[k+1]==a[i]) k++;
		pi[i]=k;
	}
	k=0;
	for(i=1;i<=m;i++)
	{	while(k&&b[i]!=a[k+1]) k=pi[k];
		if(a[k+1]==b[i]) k++;
		if(k==n)
		{	count++;
			if(count<=1000) sol[count]=i-n;
		}
	}
	//free(pi);
}

int main()
{
	citeste();
	rezolva();
	scrie();
	return 0;
}