Cod sursa(job #344359)

Utilizator serbanlupulupulescu serban serbanlupu Data 29 august 2009 19:43:14
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

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

string a;
string b;
vector<int > next;
int sol[1001];
int nr_sol;

void KMP()
{
	f>>a>>b;

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

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

	next.resize(a.size()+1);
	next[1]=0;
	int k=0;
	for (int 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 (int i=1; i<=m; ++i)
	{
		while (k>0 && a[k+1]!=b[i]) k=next[k];
		if (a[k+1] == b[i]) ++k;
		if (n==k)
			if (nr_sol < 1000)
				sol[++nr_sol]=i-k+1;
	}
}

void afisare()
{
	g<<nr_sol<<endl;
	for (int i=1; i<=nr_sol; ++i)
		g<<sol[i]<<" ";
}

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