KMP

#include <iostream>
#include <cstring>
#include <cassert>
#include <memory>
#include <ctime>

using namespace std;

bool g_bUseNormal = false;
int* next_array = nullptr;

void gen_next_array(const char* target)
{
	int tgtlen = strlen(target);
	//kmp algorithm
	//"前缀"和"后缀" 重合数目
	//"前缀"指除了最后一个字符以外，一个字符串的全部头部组合(必须是第一个元素开头)；
	//"后缀"指除了第一个字符以外，一个字符//串的全部尾部组合(必须是最后一个元素结尾)。
	//init next array
	//pre-fix , post-fix
	//sample : "abcdab"
	//"a" null;null => 0
	//"ab" a;b => 0
	//"abc" a,ab;bc,c => 0
	//"abcd" a,ab,abc;bcd,cd,d => 0
	//"abcda" a,ab,abc,abcd;dcda,cda,da,a => 1
	//"abcdab" a,ab,abc,abcd,abcde;bcdab,cdab,dab,ab,b => 1
	next_array = new int[tgtlen];
	cout<<"calc kmp next array"<<endl;
	for(int i=0;i<tgtlen;i++)
	{
		int cn = 0;
		for(int j=0;j<i;j++)
		{
			//
			int start = 0;
			int stop = 0; //=> i/2
			for(stop = 0;stop<i/2;stop++)
			{
				int m = start;
				for( ;m < stop && target[m] == target[tgtlen-m];m++){}
				
				if(m == stop){cn++;}
			}
		}
		next_array[i] = cn;
		cout<<cn<<" ";
	}
	cout<<endl;
}
//refrence : http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
int KmpMatch(const char* src,const char* target)
{
	if(!src || !target)
	{
		return -1;
	}
	int srclen = strlen(src);
	int tgtlen = strlen(target);
	if(srclen < tgtlen)
	{
		return -1;
	}
	int match = -1;
	//normal algorithm
	if(g_bUseNormal)
	{
		for(int i=0;i<(srclen-tgtlen)+1 && -1==match;i++)
		{
			int j=0;
			for(;j<tgtlen && src[i+j] == target[j];j++){}
			if(j == tgtlen)
			{
				match=i;
				break;
			}
		}
	}else
	{
		//sample : "abcdab" "cd"
		for(int i=0;i<(srclen-tgtlen)+1 && -1==match;i++)
		{
			int j=0;
			for(;j<tgtlen && src[i+j] == target[j];j++){}
			if(j == tgtlen)
			{
				match=i;
				break;
			}
			else
			{
				//skip
				i +=  next_array[j];
			}
		}
	}
	return match;
}
void test()
{
	int caseid = 0;
	cout<<"test begin ..."<<endl;
	auto casedone = [&caseid](){cout<<"test case "<<caseid++<<" OK"<<endl;};
	assert(-1 == KmpMatch(nullptr,nullptr)); casedone();
	assert(-1 == KmpMatch("hello",nullptr));casedone();
	assert(-1 == KmpMatch(nullptr,"hello"));casedone();
	assert(-1 == KmpMatch("hello","hello_long"));casedone();
	
	assert(0 == KmpMatch("hello","hello"));casedone();
	assert(5 == KmpMatch("abcd_hello","hello"));casedone();
	assert(11 == KmpMatch("abcd_hellx_hello","hello"));casedone();
	assert(42 == KmpMatch("hella_hellb_hellc_helld_helle_hellf_hellx_hello","hello"));casedone();
	cout<<"test done ..."<<endl;
}
int main(int argc,char* argv[])
{
	clock_t t1,t2;
	int testcnt = 2000000;
	streambuf* oldbuf =  nullptr;
	//normal
	oldbuf = cout.rdbuf(nullptr);
	t1 = clock();
	g_bUseNormal = true;
	for(int i=0;i<testcnt;i++)
	{
		test();
	}
	t2 = clock();
	oldbuf = cout.rdbuf(oldbuf);
	cout<<"normal method cose time : "<<t2-t1<<endl;
	
	//kmp
	oldbuf = cout.rdbuf(nullptr);
	gen_next_array("hello");
	t1 = clock();
	g_bUseNormal = false;
	for(int i=0;i<testcnt;i++)
	{
		test();
	}
	t2 = clock();
	oldbuf = cout.rdbuf(oldbuf);
	cout<<"kmp method cose time : "<<t2-t1<<endl;
	delete[] next_array;
	return 0;
}