Attempt at implementing fast string search algorithms, with naive search there for reference

string-search.cxx

#include <iostream>
#include <cstdlib>

#include "pretty_print.hxx"

using namespace std;

static inline bool naive(char* haystack, char* needle) {
	for (int i = 0; haystack[i] != '\0'; ++i) {
		if (haystack[i] == needle[0]) {
			for (int j = 0; haystack[i] != '\0' && haystack[i + j] == needle[j]; ++j) {
				if (needle[j] == '\0') {
					return true;
				}
			}
		}
	}

	return false;
}

static inline bool KMP(char* haystack, char* needle) {
	int m, n, j;

	for (m = 0, n = 0; haystack[m] != '\0'; ++m) {
		if (haystack[m] == needle[0]) {
			for ((j = n), n = 0; haystack[m] != '\0' && haystack[m + j] == needle[j]; ++j) {
				if (needle[j] == '\0') {
					return true;
				}

				if (haystack[m + j + n + 1] == needle[n]) {
					n = j;
				}
			}

			if (n == 0) {
				n = j;
			}
		}
	}

	return false;
}

int main() {
	char haystack[] = "ABC ABCDAB ABCDABCDABDEABCABCDABD";
	char needle[] = "ABCDABD";

	cout << "Haystack: " << haystack << endl;
	cout << "Needle: " << needle << endl;
	cout << "Returned value: " << std::boolalpha << KMP(haystack, needle) << endl;

	return EXIT_SUCCESS;
};