Cod sursa(job #432250)

Utilizator NemultumituMatei Ionita Nemultumitu Data 1 aprilie 2010 23:49:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char a[2000010],b[2000010];
int n,m,cnt,pia[2000010];
vector <int> poz;

void citire()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	gets(a);
	gets(b);
	n=strlen(a);
	m=strlen(b);
	for (int i=n;i;--i)
		a[i]=a[i-1];
	a[0]='$';
	for (int i=m;i;--i)
		b[i]=b[i-1];
	b[0]='$';
}

int main()
{
	citire();
	int i;
	for (i=2;a[i];++i)
	{
		int y=pia[i-1];
		while (a[y+1]!=a[i]&&y)
			y=pia[y];
		if (a[y+1]==a[i])
			pia[i]=y+1;
	}
	int aux=0;
	for (int i=1;b[i];++i)
	{
		int y=aux;
		while (a[y+1]!=b[i]&&y)
			y=pia[y];
		if (a[y+1]==b[i])
			aux=y+1;
		else
			aux=0;
		if (aux==n)
		{
			++cnt;
			if (poz.size()<1000)
				poz.push_back(i-n);
		}
	}
	printf("%d\n",cnt);
	for (int i=0;i<poz.size();++i)
		printf("%d ",poz[i]);
	printf("\n");
	return 0;
}