/*
 * KnuthMorrisPratt.h
 *
 *  Created on: 5. 11. 2014
 *      Author: Jan Travnicek
 */

#ifndef _ARBOLOGY_KNUTH_MORRIS_PRATT_H_
#define _ARBOLOGY_KNUTH_MORRIS_PRATT_H_

#include <set>
#include <common/multipleDispatch.hpp>
#include <tree/TreeFeatures.h>

namespace arbology {

namespace exact {

/**
 * Implementation of BMH for MI(E+\eps)-EVY course 2014
 * To get rid of zeros in BCS table we ignore last haystack character
 */
class KnuthMorrisPratt : public std::DoubleDispatch < std::set < unsigned >, tree::TreeBase, tree::TreeBase > {
public:
	/**
	 * Search for pattern in linear string.
	 * @return set set of occurences
	 */
	static std::set < unsigned > match ( const tree::Tree & subject, const tree::Tree & pattern );

	static std::set < unsigned > match ( const tree::PrefixRankedBarTree & subject, const tree::PrefixRankedBarTree & pattern );
	static std::set < unsigned > match ( const tree::PrefixRankedBarTree & subject, const tree::PrefixRankedBarPattern & pattern );

	static std::set < unsigned > match ( const tree::PrefixRankedTree & subject, const tree::PrefixRankedTree & pattern );
	static std::set < unsigned > match ( const tree::PrefixRankedTree & subject, const tree::PrefixRankedPattern & pattern );

	static KnuthMorrisPratt & getInstance ( ) {
		static KnuthMorrisPratt res;

		return res;
	}

};

} /* namespace exact */

} /* namespace arbology */

#endif /* _ARBOLOGY_KNUTH_MORRIS_PRATT_H_ */