Cod sursa(job #344357)

Utilizator serbanlupulupulescu serban serbanlupu Data 29 august 2009 19:37:41
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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;
vector<int > sol;
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());
	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)
			{
				++nr_sol;
				sol.push_back(i-k+1);
			}
	}
}

void afisare()
{
	g<<nr_sol<<endl;
	vector<int >::iterator it;
	for (it=sol.begin(); it<sol.end(); it++)
		g<<*it<<" ";
}

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