Cod sursa(job #338673)

Utilizator prdianaProdan Diana prdiana Data 6 august 2009 15:03:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <vector>
#include <string.h>
#define MAXN 2000002

using namespace std;
char a[MAXN],b[MAXN];
int pi[MAXN];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	vector<int> sol;
	int sza,szb,i,k = -1,ss = 0;
	
	scanf("%s",&a);
	sza = strlen(a);
	scanf("%s",&b);
	szb = strlen(b);

	pi[0] = -1;
	for (i=1;i<sza;i++)
	{
		while (k>-1 && a[i] != a[k+1])
		{
			k = pi[k];
		}
		if (a[i] == a[k+1])
		{
			k++;
		}
		pi[i] = k;
	}
	k = -1;
	for (i=0;i<szb;i++)
	{
		while (k>-1 && b[i] != a[k+1])
		{
			k = pi[k];
		}
		if (b[i] == a[k+1])
		{
			k++;
		}
		if (k == sza-1)
		{
			ss++;
			if (sol.size() < 1000)
			{
				sol.push_back(i-sza+1);
			}
			k = pi[k];
		}
	}

	printf("%d\n",ss);
	for (i=0;i<sol.size();i++)
	{
		printf("%d ",sol[i]);
	}

	return 0;
}