Cod sursa(job #338669)

Utilizator prdianaProdan Diana prdiana Data 6 august 2009 14:52:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
#include <vector>
#include <string.h>
#define MAXN 20000

using namespace std;

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	char a[MAXN],b[MAXN];
	int pi[MAXN];
	vector<int> sol;
	int sza,szb,i,k;
	
	scanf("%s",&a);
	sza = strlen(a);
	scanf("%s",&b);
	szb = strlen(b);

	pi[0] = -1;
	k = -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)
		{
			sol.push_back(i-sza+1);
			k = pi[k];
		}
	}

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

	return 0;
}