Cod sursa(job #616079)

Utilizator selea_teodoraSelea Teodora selea_teodora Data 11 octombrie 2011 17:55:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<stdio.h>
#include<string.h>
using namespace std;
int pi[2000005],pos[2000005],n,m,j;
char a[2000005],b[2000005];
void calcul_prefix()
{
	int k=0,i;
	for(i=2;i<=n;i++)
		{
			while(k>0&&a[i]!=a[k+1])
				k=pi[k];
			if(a[i]==a[k+1])
				++k;
			pi[i]=k;
	}
}
void potrivire()
{
	int k=0,i;
	for(i=1;i<=m;i++)
	{
		while(k>0&&b[i]!=a[k+1])
			k=pi[k];
		if(b[i]==a[k+1])
			++k;
		if(k==n)
		{
			
			k=pi[n];
			++j;
			if(j<=1000)
				pos[j]=i-n;
		}
	}
}
int main()
{
	freopen ("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(a,sizeof(a),stdin);
	fgets(b,sizeof(b),stdin);
	while(a[n]<='Z'&&a[n]>='A'||a[n]<='z'&&a[n]>='a'||a[n]<='9'&&a[n]>='0')
		++n;
	while(b[m]<='Z'&&b[m]>='A'||b[m]<='z'&&b[m]>='a'||b[m]<='9'&&b[m]>='0')
		++m;
	int i;
	for(i=n;i>0;i--)
		a[i]=a[i-1];
	a[0]=' ';
	for(i=m;i>0;i--)
		b[i]=b[i-1];
	b[0]=' ';
	calcul_prefix();
	potrivire();
	printf("%d\n",j);
	for(i=1;i<=j;i++)
		printf("%d ",pos[i]);
	printf("\n");
	return 0;
}