DeadZoneUsingBadCharacterShift.cpp

/*
 * DeadZoneUsingBadCharacterShift.cpp
 *
 *  Created on: 5. 11. 2014
 *      Author: Radomir Polach, Tomas Pecka
 */

#include "DeadZoneUsingBadCharacterShift.h"
#include "BadCharacterShiftTable.h"
#include "ReversedBadCharacterShiftTable.h"

#include <exception/AlibException.h>
#include <string/LinearString.h>
#include <alphabet/Symbol.h>

#include <map>

namespace stringology {

namespace exact {

std::set < unsigned > DeadZoneUsingBadCharacterShift::match ( const string::String & subject, const string::String & pattern ) {
	return getInstance ( ).dispatch ( subject.getData ( ), pattern.getData ( ) );
}

std::set < unsigned > DeadZoneUsingBadCharacterShift::match ( const string::LinearString & string, const string::LinearString & pattern ) {
	std::set < unsigned > occ;
	std::map < alphabet::Symbol, size_t > fbcs = BadCharacterShiftTable::bcs ( pattern );     // NOTE: the subjects alphabet must be a subset or equal to the pattern
	std::map < alphabet::Symbol, size_t > bbcs = ReversedBadCharacterShiftTable::bcs ( pattern ); // NOTE: the subjects alphabet must be a subset or equal to the pattern

	match_rec ( occ, string, pattern, fbcs, bbcs, 0, string.getContent ( ).size ( ) - pattern.getContent ( ).size ( ) + 1 );
	return occ;
}

void DeadZoneUsingBadCharacterShift::match_rec ( std::set < unsigned > & occ, const string::LinearString & string, const string::LinearString & pattern, std::map < alphabet::Symbol, size_t > & fbcs, std::map < alphabet::Symbol, size_t > & bbcs, int low, int high ) {
	if ( low >= high ) return;

	int middle = ( low + high ) / 2;
	size_t i = 0;

	while ( i < pattern.getContent ( ).size ( ) && string.getContent ( )[middle + i] == pattern.getContent ( )[i] )
		i++;

	 // Yay, there is match!!!
	if ( i == pattern.getContent ( ).size ( ) ) occ.insert ( middle );

	match_rec ( occ, string, pattern, fbcs, bbcs, low, middle - bbcs[string.getContent ( )[middle]] + 1 );
	match_rec ( occ, string, pattern, fbcs, bbcs, middle + fbcs[string.getContent ( )[middle + pattern.getContent ( ).size ( ) - 1]], high );
}

auto DeadZoneUsingBadCharacterShiftLinearStringLinearString = DeadZoneUsingBadCharacterShift::RegistratorWrapper < std::set < unsigned >, string::LinearString, string::LinearString > ( DeadZoneUsingBadCharacterShift::getInstance ( ), DeadZoneUsingBadCharacterShift::match );

} /* namespace exact */

} /* namespace stringology */