stringmarch.cpp

数据结构的转换,包括字符串结构的变换等功能

#include "string.h"
#include "StringMarch.h"

StringMarch::StringMarch()
:_StringLength(0)
,_PatternLength(0)
,_String(NULL)
,_Pattern(NULL)
,_NextValue(NULL)
{
}

StringMarch::~StringMarch()
{
	delete [] _String;
	delete [] _Pattern;
	delete [] _NextValue;
}

bool StringMarch::getNextValue()
{
	if(_PatternLength==0)
		return false;

	delete [] _NextValue;
	_NextValue=new int[_PatternLength];

	_NextValue[0]=0;
	for(int i=1,int j=0;i<_PatternLength;i++,j++)
	{
		if(_Pattern[i]==_Pattern[j])
			_NextValue[i]=_NextValue[j];
		else
		{
			_NextValue[i]=j;
			j=-1;
		}
	}

	return true;
}

bool StringMarch::initialize(char *s,char *p)
{
	_StringLength=strlen(s);
	_PatternLength=strlen(p);
	if(_StringLength==0||_PatternLength==0)
		return false;

	delete[] _String;
	delete[] _Pattern;
	_String=new char[_StringLength+1];
	_Pattern=new char[_PatternLength+1];
	strcpy(_String,s);
	strcpy(_Pattern,p);

	return true;
}

int StringMarch::march()
{
	getNextValue();

	for(int i=0,int j=0;i<_StringLength&&j<_PatternLength;)
	{
		if(_String[i]!=_Pattern[j])
		{
			if(j==0)
				i++;
			else
				j=_NextValue[j];

			//if(j==0)
			//	i++;
			//else
			//	j=_NextValue[j];
		}
		
		else
		{
			i++;
			j++;
		}
	}
	if(j==_PatternLength)
		return i-j;
	else
		return -1;
}