Cod sursa(job #1283974)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 6 decembrie 2014 09:53:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

void zAlgorithm(const string& s, const size_t sz, vector<size_t>& shifts)
{
	vector<size_t> z(s.size(), 0);

	size_t L = 0, R = 0;
	z[0] = s.size();
	for (size_t i = 1; i < s.size(); ++i)
	{
		//Find new interval [L, R]
		if (i > R)
		{
			L = R = i;
			while (R < s.size() && s[R] == s[R - L])
				++R;
			--R;	//because R will be bigger by 1
			z[i] = R - L + 1;
		}
		else
		{
			size_t k = i - L;
			if (z[k] < R - i + 1)
				z[i] = z[k];
			else		//R is already bigger than i
			{
				L = i;
				while (R < s.size() && s[R] == s[R - L])
					++R;
				--R;
				z[i] = R - L + 1;
			}
		}
	}
	for (size_t i = 0; i < z.size(); ++i)
		if (z[i] == sz)
			shifts.push_back(i - sz - 1);
}

int main()
{
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	
	string p, t, s;
	fin >> p >> t;
	s = p + '$' + t;
	vector<size_t> shifts;
	
	zAlgorithm(s, p.size(), shifts);
	fout << shifts.size() << '\n';
	for (size_t i = 0; i < min(shifts.size(), size_t(1000)); ++i)
		fout << shifts[i] << ' ';
	fout << '\n';

	return 0;
}