BorderArray.h

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

#ifndef _BORDER_ARRAY_H_
#define _BORDER_ARRAY_H_

#include <alib/vector>
#include <string/LinearString.h>

namespace string {

namespace properties {

class BorderArray {
public:
	/**
	 * Computes border array of string
	 * @param string string to compute border array for
	 * @return Vector of length same as string, where i-th index corresponds to i-th element of string
	 */
	template < class SymbolType >
	static ext::vector<unsigned> construct(const string::LinearString < SymbolType >& string);
};

template < class SymbolType >
ext::vector<unsigned> BorderArray::construct(const string::LinearString < SymbolType >& string) {
	const auto& w = string.getContent();
	ext::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;
}

} /* namespace properties */

} /* namespace string */

#endif /* _BORDER_ARRAY_H_ */