qsearchstr.h

一种改进的Boyer-Moore的字符串查找算法

class CQSearchStr
{
   //static const int MAXCHAR = 256;
public:
   int m_iShiftTable[256];
   int m_iCompLen;
   unsigned char* m_pbPatt;       //pattern
   CQSearchStr(unsigned char *patt, int iCompLen);
   ~CQSearchStr();
public:
   int QSearch(unsigned char *pData, int iDataLen);
};

CQSearchStr::CQSearchStr(unsigned char *patt, int iCompLen)
{
	if( iCompLen >256 )   // max match Lenth
	{ 
		m_pbPatt=NULL; 
		return;
	}   
	int i;
	m_pbPatt=new unsigned char [iCompLen+1];
	for(i = 0; i < iCompLen; i++ ) 
		m_pbPatt[i] = patt[i];
	m_iCompLen=iCompLen;
	// construct delta shift table
    for(i = 0; i < 256; i++)   m_iShiftTable[i]=m_iCompLen+1;
	for(i = 0 ; i < iCompLen; i++) m_iShiftTable[patt[i]] = iCompLen - i ;
}

CQSearchStr::~CQSearchStr()
{
	delete[] m_pbPatt;
}

int CQSearchStr::QSearch(unsigned char *pData, int iDataLen)
{
	if( (m_pbPatt==NULL) || (m_iCompLen<2) ) return -3;
	if( m_iCompLen >= iDataLen ) return -2;

    // start searching...
    // the main searching loop	
    int i,j,k;
	k = m_iCompLen - 1;
	while (k <= iDataLen) 
	{
		j = m_iCompLen - 1;
		i = k; 
        while (j >= 0 && pData[i] == m_pbPatt[j]) 
		{
			j--;
			i--;
		}
		if (j < 0)
			return (i+1);
		k += m_iShiftTable[pData[k+1]];
	}
	return -1;
}