Knuth–Morris–Pratt algorithm in c++

kmp.cpp

#include <iostream>
#include <algorithm>
using namespace std;

int find_substring(string str, string pattern) {

	// Step 0. Should not be empty string
	if( str.size() == 0 || pattern.size() == 0)
		return -1;

	// Step 1. Compute failure function
	int failure[pattern.size()];
	std::fill( failure, failure+pattern.size(), -1);

	for(int r=1, l=-1; r<pattern.size(); r++) {

		while( l != -1 && pattern[l+1] != pattern[r])
			l = failure[l];

		// assert( l == -1 || pattern[l+1] == pattern[r]);
		if( pattern[l+1] == pattern[r])
			failure[r] = ++l;
	}

	// Step 2. Search pattern
	int tail = -1;
	for(int i=0; i<str.size(); i++) {

		while( tail != -1 && str[i] != pattern[tail+1])
			tail = failure[tail];

		if( str[i] == pattern[tail+1])
			tail++;

		if( tail == pattern.size()-1)
			return i - tail;
	}

	return -1;
}

int main() {

	cout << find_substring("abcd", "abcd") << endl;
	cout << find_substring("abcd", "ab") << endl;
	cout << find_substring("ab", "abcd") << endl;
	cout << find_substring("ababc", "abc") << endl;

	return 0;
}

Is this algorithm fast?

@SavicStefan
The algorithm is good enough for general purpose, with complexity O(n). See also wikipedia.

That said, I didn't test this implementation extensively( I code it on geeksforgeeks and passed), that's all I can say.

Thanks for your attention.