パターンマッチングKMPアルゴリズム詳細

/*
 *	KMP       
 */

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

/*
 *	      next  
 *	       ，     ，    
 *	      O(m)，m       
 */
void countNext(char* strPattern, int len, int* next)
{
	int i = 0, j = -1;
	next[i] = j;
	while (i < len-1)
	{
		if (j == -1)
		{
			i++;
			j++;
			next[i] = j;
		} else if (strPattern[i] == strPattern[j]) {
			i++;
			j++;
			if (strPattern[i] != strPattern[j])
			{
				next[i] = j;
			} else {
				next[i] = next[j];
			}
		} else {
			j = next[j];
		}
	}
}

/*
 *	  KMP        
 *	KMP         O(n)+O(m) = O(n+m)
 *	  n      ，m       ，     next  
 *	KMP                 ，         
 *	           ，       ，     ，     
 *	              ，          ，      KMP   
 */
int indexKMP(char* strMain, int lenMain, char* strPattern, int lenPattern, int pos, int* next)
{
	int i = pos, j = 0;
	while (i < lenMain && j < lenPattern)
	{
		if (j == -1 || strMain[i] == strPattern[j])
		{
			i++;
			j++;
		} else {
			j = next[j];
		}
	}

	if (j >= lenPattern)
	{
		return i - lenPattern;
	}

	return -1;
}


int main()
{
	char* strPattern = "abce";
	char* strMain = "ksekabcedwfabcekf";
	int lenMain = strlen(strMain);
	int lenPattern = strlen(strPattern);

	int* next = new int[lenPattern];
	countNext(strPattern, lenPattern, next);

	int startPos = 5;
	int pos = indexKMP(strMain, lenMain, strPattern, lenPattern, startPos, next);
	
	if (pos < 0)
	{
		cout<<"     "<<strMain<<"    "<<startPos+1<<"             "<<strPattern<<endl;
	} else {
		cout<<"     "<<strMain<<"    "<<startPos+1<<"           "<<strPattern<<"    "<<pos+1
				<<"    "<<endl;
	}

	delete[] next;
	return 0;
}