Cod sursa(job #425650)

Utilizator NemultumituMatei Ionita Nemultumitu Data 25 martie 2010 22:03:55
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char a[2000050],b[2000050];
int pia[2000050],pib[2000050];
int cnt;
vector <int> poz;

int main()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	gets(a);
	gets(b);
	int i;
	for (i=1;a[i];++i)
	{
		if (a[i]==a[0])
			pia[i]=1;
		int y=i-1;
		while (y+1)
		{
			if (a[pia[y]]==a[i]&&pia[y]+1>pia[i])
				pia[i]=pia[y]+1;
			y=pia[y]-1;
		}
	}
	int n=i;
	if (b[0]==a[0])
		pib[0]=1;
	bool k;
	for (i=1;b[i];++i)
	{
		k=0;
		if (b[i]==a[0])
			pib[i]=1;
		int y=pia[pib[i-1]-1];
		if (a[pib[i-1]]==b[i])
		{
			pib[i]=pib[i-1]+1;
			if (pib[i]==n)
				poz.push_back(i);
			continue;
		}
		while (y&&!k)
		{
			if (a[y]==b[i])
			{
				pib[i]=y+1;
				k=1;
			}
			y=pia[y-1];
		}
		if (pib[i]==n)
			poz.push_back(i);
	}
	printf("%d\n",poz.size());
	cnt=0;
	for (i=0;i!=poz.size()&&i!=1000;++i)
		printf("%d ",poz[i]-n+1);
	printf("\n");
	return 0;
}