stdafx.cpp

字符匹配中的KMP算法

// stdafx.cpp : source file that includes just the standard includes
//	GetNext.pch will be the pre-compiled header
//	stdafx.obj will contain the pre-compiled type information

#include "stdafx.h"
#include <iostream.h>
#include <string.h>
#include <iomanip.h>
// TODO: reference any additional headers you need in STDAFX.H
// and not in this file
int* GetNext(char *a)
{
	int iMainStrCount = 1;
	int iSubStrCount  = 0;
	int iStrLen       = (int)strlen(a);
	int *pNextVal = new int[iStrLen];
	pNextVal[0] = iStrLen;
	pNextVal[1] = 0;
//    cout << "next[" << 1 << "]" << setw(6) << pNextVal[1] <<endl;
	while (iMainStrCount < iStrLen)
	{
		if ((a[iMainStrCount-1] == a[iSubStrCount-1]) || (iSubStrCount == 0))
		{
			iMainStrCount++;
			iSubStrCount++;
			pNextVal[iMainStrCount] = iSubStrCount;			
//			cout << "next[" << iMainStrCount << "]" << setw(6) << pNextVal[iMainStrCount] << endl;
		}
		else
			iSubStrCount = pNextVal[iSubStrCount];
	}
	return pNextVal;
}

void KMPstr (char *pMatStr, char *pSubStr, int next[])
{
	int iMatNonius = 0;
	int iSubNonius = 0;

	int iMatLen = strlen(pMatStr);
	int iSublen = strlen(pSubStr);
	while (iMatNonius<iMatLen && iSubNonius<iSublen)
	{
		if (pMatStr[iMatNonius] == pSubStr[iSubNonius] || iSubNonius==0)
		{
			iMatNonius++;
			iSubNonius++;
		}
		else
			iSubNonius = next[iSubNonius];
	}

	if (iSubNonius == iSublen)
	{
		cout << "SUCC, matchable position is" << setw(2) << iMatNonius-iSubNonius << endl;
	}
	else
		cout << "FAIL" << endl;
}