Cod sursa(job #344543)

Utilizator serbanlupulupulescu serban serbanlupu Data 30 august 2009 15:21:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
//KMP

#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <Cstdio>

using namespace std;

#define N 2000009

char a[N];
char b[N];

int next[N];
int nr_sol;
int sol[1010];

int max(int i, int j)
{
	if (i > j)
		return i;
	else
		return j;
}

void KMP()
{
	//fstream f("strmatch.in", ios::in);
	//fstream g("strmatch.out", ios::out);

	//f>>a;
	//f>>b;
	freopen("strmath.in", "r", stdin);
	freopen("strmath.out", "w", stdout);
	gets(a);
	gets(b);
	int lenght_a=strlen(a);
	int lenght_b=strlen(b);

	int i,j;

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

	for (j=lenght_b; j>=0; --j)
		b[j+1]=b[j];
	
	int k=0;
	next[1]=0;
	for (i=2; i<=strlen(a); ++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<=lenght_b; ++i)
	{
		while (k>0 && a[k+1]!=b[i]) k=next[k];
		if (a[k+1]==b[i]) ++k;
		if (k==lenght_a)
		{
			if (nr_sol<1000)
				sol[++nr_sol]=i-lenght_a;
			else 
				++nr_sol;
		}
	}

	//g<<nr_sol<<"\n";
	printf("%d ",nr_sol);
	for (i=1;i<=min(nr_sol,1000);++i)
		printf("%d ",sol[i]);//g<<sol[i]<<" ";
	//f.close();
	//g.close();
}

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