boyer_moore.cpp

/* classic boyer_moore find algorithm
 * by pewniak747@gmail.com */

#include<iostream>

int boyer_moore(std::string input, std::string pattern) {
	int index = 0;
	int input_length = input.size()-1;
	int pattern_length = pattern.size()-1;
	int last[255];
	
	for(int i=0; i < 255; i++) last[i] = -1;
	for(int i=0; i <= pattern_length; i++) last[(int)pattern[i]] = i;
	
	while(index <= input_length-pattern_length) {
		int j = pattern_length;
		bool match = true;
		
		for(j; j >= 0; j--) {
			if(pattern[j] != input[index+j]) {
				match = false;
				break;
			}
		}
		
		//std::cout << "assertion: index " << index << " j " << j << "\n";
		
		if(match) return index;
		else if(last[pattern[j]] == -1) index += pattern_length;
		else if(j-last[pattern[j]] > 0) index += j-last[pattern[j]];
		else index++;
	}
	
	return -1;
}

int main() {
	std::cout << "boyer-moore find\nall tests should be 1\n";
	//passing tests
	std::cout << int(boyer_moore("fksdbogheohogh", "heo") != -1) << "\n";
	std::cout << int(boyer_moore("ifgu fhvnwov.b liawgbvmzvsiwl", "b") != -1) << "\n";
	std::cout << int(boyer_moore("tomaszPeWinski", "ski") != -1) << "\n";
	std::cout << int(boyer_moore("looalbiheihgoalllllasdghsjadghwoe", "asdghsja") != -1) << "\n";
	std::cout << int(boyer_moore("nomaoamafnafnannananananana", "nananana") != -1) << "\n";
	std::cout << int(boyer_moore("ooooooaoaoaaaaa", "oa") != -1) << "\n";
	//failing tests
	std::cout << int(boyer_moore("a;ghodvhkjshghsogkhdkjghohgohsdgh", "p") == -1) << "\n";
	std::cout << int(boyer_moore("a;ghodvhkjshghsogkhdkjghohgohsdgh", "sdfghj") == -1) << "\n";
	std::cout << int(boyer_moore("a;ghodvhkjshghsogkhdkjghohgohsdgh", "pkjbvderty") == -1) << "\n";
	std::cout << int(boyer_moore("a;ghodvhkjshghsogkhdkjghohgohsdgh", "sdfhdfh dshf ") == -1) << "\n";
	std::cout << int(boyer_moore("a;ghodvhkjshghsogkhdkjghohgohsdgh", "jffff") == -1) << "\n";
}