Cod sursa(job #729261)

Utilizator marius21Petcu Marius marius21 Data 29 martie 2012 13:52:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <string>
#include <vector>
#include <fstream>
using namespace std;

#define MAX_STR 2000000

void read(string & a, string & b)
{
	a.reserve(MAX_STR);
	b.reserve(MAX_STR);
	ifstream f("strmatch.in");
	f>>a>>b;
}

void write(const vector<int> & res)
{
	ofstream f("strmatch.out");
	size_t n = res.size();
	f<<n<<'\n';
	for (size_t i=0; i<n; i++)
		f<<res[i]<<' ';
}

void solve(const string & a, const string & b, vector<int> & res)
{
	res.reserve(1024);
	size_t sa = a.size();
	size_t sb = b.size();
	
	vector<int> t;
	t.reserve(sa+1);
	t.push_back(-1);
	t.push_back(0);
	size_t cand = 0;
	for (size_t i = 2; i<=sa;)
	{
		if (a[cand] == a[i-1])
		{
			t.push_back(t[i-1]+1);
			i++; cand++;
		} else {
			if (cand)
				cand = t[cand];
			else {
				t.push_back(0);
				i++;
			}
		}
	}
	
	size_t i,m;
	for (m = 0, i = 0; m+i < sb;)
	{
		if (i < sa && a[i] == b[i+m])
		{		
			i++;
			if (i==sa)
				res.push_back(m);
		} else {
			m = m + i - t[i];
			if (t[i] >= 0)
				i = t[i];
			else
				i = 0;
		}
	}
}

int main()
{
	string a,b;
	vector<int> results;
	read(a,b);
	solve(a,b,results);
	write(results);
	return 0;
}