import std.stdio;

int bruteForceSchemey(string pat, string str, int start = 0) {
	int loop(int strOff, int patOff) {
		if(strOff == str.length && patOff != pat.length) {
			return -1;
		} else if(patOff == pat.length) {
			return strOff - patOff;
		} else if(str[strOff] == pat[patOff]) {
			return loop(strOff + 1, patOff + 1);
		} else {
			return loop(strOff - patOff + 1, 0);
		}
	}
	
	return loop(start, 0);
}

int bruteForceImperative(string pat, string str, int start = 0) {
	int strOff = start; 
	int patOff = 0;
	
	while(strOff != str.length) {
		if(patOff == pat.length) {
			break;
		} else if(str[strOff] == pat[patOff]) {
			strOff++;
			patOff++;
		} else {
			strOff = strOff - patOff + 1;
			patOff = 0;
		}
	}
	
	return patOff == pat.length ? strOff - patOff : -1;
}

int bruteForceNestedLoops(string pat, string str, int start = 0) {
	
	foreach(stridx, strch; str[start..$]) {
		
		bool found = true;
		foreach(patidx, patch; pat) {
			if(stridx + patidx >= str.length) {
				found = false;
				break;
			}
			if(patch != str[start + stridx + patidx]) {
				found = false;
				break;
			}
		}
		
		if(found) {
			return stridx + start;
		}
		
	}
	return -1;
}

typedef int function(string, string, int) SearchFunction;

void testSearch(string name, SearchFunction fn) {
	writefln("Testing search using %s algorithm", name);
	
	auto pp = "Programming Praxis";
	
	testSearchStr(fn, pp, pp, 0);
	testSearchStr(fn, "Praxis", pp, 12);
	testSearchStr(fn, "Prax", pp, 12);
	testSearchStr(fn, "praxis", pp, -1);
	testSearchStr(fn, "P", pp, 0);
	testSearchStr(fn, "P", pp, 12, 5);
	testSearchStr(fn, "mi", pp, 7);
	
	writefln();
}

void testSearchStr(SearchFunction fn, string pat, string str, int expected, int start = 0) {
	writefln("%s[%s] == %d [%d]", str, pat, expected, fn(pat, str, start));
	assert(fn(pat, str, start) == expected);
}

void main() {
	testSearch("brute force (schemey)", &bruteForceSchemey);
	testSearch("brute force (imperative)", &bruteForceImperative);
	testSearch("brute force (nested loops)", &bruteForceNestedLoops);
}

Testing search using brute force (schemey) algorithm
Programming Praxis[Programming Praxis] == 0 [0]
Programming Praxis[Praxis] == 12 [12]
Programming Praxis[Prax] == 12 [12]
Programming Praxis[praxis] == -1 [-1]
Programming Praxis[P] == 0 [0]
Programming Praxis[P] == 12 [12]
Programming Praxis[mi] == 7 [7]

Testing search using brute force (imperative) algorithm
Programming Praxis[Programming Praxis] == 0 [0]
Programming Praxis[Praxis] == 12 [12]
Programming Praxis[Prax] == 12 [12]
Programming Praxis[praxis] == -1 [-1]
Programming Praxis[P] == 0 [0]
Programming Praxis[P] == 12 [12]
Programming Praxis[mi] == 7 [7]

Testing search using brute force (nested loops) algorithm
Programming Praxis[Programming Praxis] == 0 [0]
Programming Praxis[Praxis] == 12 [12]
Programming Praxis[Prax] == 12 [12]
Programming Praxis[praxis] == -1 [-1]
Programming Praxis[P] == 0 [0]
Programming Praxis[P] == 12 [12]
Programming Praxis[mi] == 7 [7]