Cod sursa(job #344365)

Utilizator serbanlupulupulescu serban serbanlupu Data 29 august 2009 20:07:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

#define NMAX 2000010

char a[NMAX];
char b[NMAX];
int next[NMAX];
int sol[1020];
int nr_sol;

fstream f("strmatch.in", ios::in);
fstream g("strmatch.out", ios::out);

void KMP()
{
	f>>a;
	f>>b;
	int n=strlen(a);
	int m=strlen(b);

	for (int i=n; i>=0; --i)
		a[i+1]=a[i];

	for (int i=m; i>=0; --i)
		b[i+1]=b[i];

	int k=0;
	int i;
	next[1]=0;
	for (i=2; i<=n ;++i)
	{
		while ( k>0 && a[k+1]!=a[i] ) k=next[k];
		if (a[k+1]==a[i]) ++k;
		next[i]=k;
	}

	k=0;

	for (i=1; i<=m; ++i)
	{
		while ( k>0 && a[k+1]!=b[i] ) k=next[k];
		if (a[k+1]==b[i]) ++k;
		if (k==n)
			if ( nr_sol<1000 )
				sol[++nr_sol]=i-k;
	}
	
	if (nr_sol!=0)
	{
		if (nr_sol<1000)
		{
			g<<nr_sol<<"\n";
			for (int i=1; i<=nr_sol; ++i)
				g<<sol[i]<<" ";
		}
		else
		{
			g<<"1000";
			for (int i=1; i<=1000; ++i)
				g<<sol[i]<<" ";
		}
	}
	else
		g<<nr_sol;

	f.close();
	g.close();
}

int  main()
{
	KMP();
	return 0;
}