#pragma once

#include <alib/measure>

#include <alib/set>
#include <alib/vector>

#include <string/LinearString.h>

namespace stringology::exact {


/**
* Implementation of the QuiteNaive algorithm from article “ IT’S ECONOMY, STUPID! ” : SEARCHING FOR A SUBSTRING
* WITH CONSTANT EXTRA SPACE COMPLEXITY
* Domenico Cantone and Simone Faro
*/
class QuiteNaive{
public:
	/**
	 * Search for pattern in linear string.
	 * @return set set of occurences
	 */
	template < class SymbolType >
	static ext::set < unsigned > match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern );
};

template < class SymbolType >
ext::set < unsigned > QuiteNaive::match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern ) {
	ext::set < unsigned > occ;
	const auto & text = subject.getContent();
	const auto & pat = pattern.getContent();
	size_t n = text.size();
	size_t m = pat.size();

	measurements::start ( "Preprocess", measurements::Type::PREPROCESS );
	// Preprocessing
	size_t gamma = 1;
	size_t delta = 1;
	while ( delta < m && pat[m-1] != pat[m-1-delta])
		++ delta;
	while ( gamma < m && pat[m-1] == pat[m-1-gamma])
		++ gamma;
	measurements::end();

	measurements::start ( "Algorithm", measurements::Type::ALGORITHM );
	// Searching
	size_t s = 0;
	while ( s <= n - m ){
		if ( pat[m-1] != text[s+m-1] ) {
			s += gamma;
		} else {
			// Note: loop here goes in other direction than in the paper
			size_t j = 0;
			while ( j + 2 <= m && pat[j] == text[s+j] )
				++ j;

			if ( j + 2 > m )
				occ.insert(s);
			s += delta;
		}
	}

	measurements::end();
	return occ;
}

} /* namespace stringology::exact */