Cod sursa(job #344368)

Utilizator serbanlupulupulescu serban serbanlupu Data 29 august 2009 20:22:41
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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;


void KMP()
{
	fstream f("strmatch.in", ios::in);
	fstream g("strmatch.out", ios::out);
	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;
			else ++nr_sol;
	}
	
	g<<nr_sol;
	if (nr_sol>1000)
		for (i=1; i<=1000; ++i)
			g<<sol[i]<<" ";
	else
		for (i=1; i<=nr_sol; ++i)
			g<<sol[i]<<" ";

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

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