BorderArray.cpp

/*
 * BorderArray.cpp
 *
 *  Created on: 1. 11. 2014
 *      Author: Tomas Pecka
 */

#include "BorderArray.h"

#include <container/ObjectsVector.h>
#include <container/ObjectsPair.h>
#include <string/String.h>
#include <primitive/Integer.h>
#include <string/LinearString.h>

namespace stringology {

namespace exact {

std::vector<unsigned> BorderArray::construct(const string::String& string) {
	return dispatch(string.getData());
}

std::vector<unsigned> BorderArray::construct(const string::LinearString& string) {
	const auto& w = string.getContent();
	std::vector<unsigned> res(w.size() + 1);

	res[0] = 0;
	res[1] = 0;
	for(size_t i = 1; i < w.size(); i++) {
		unsigned b = res[i];
		while (b > 0 && w[i + 1 - 1] != w[b + 1 - 1])
			b = res[b];

		if(w[i + 1 - 1] == w[b + 1 - 1])
			res[i + 1] = b + 1;
		else
			res[i + 1] = 0;
	}

	return res;
}

auto BorderArrayLinearString = BorderArray::RegistratorWrapper<std::vector<unsigned>, string::LinearString>(BorderArray::construct);

} /* namespace exact */

} /* namespace stringology */