morrispratt.cpp

多种字符串匹配算法 多种字符串匹配算法

// MorrisPratt.cpp: implementation of the MorrisPratt class.
//
//////////////////////////////////////////////////////////////////////

#include "MorrisPratt.h"
#include <stdio.h>
#include <string.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

MorrisPratt::MorrisPratt() : m_pNum(0), m_mpNext(NULL)
{}

MorrisPratt::~MorrisPratt()
{
	delete [] m_mpNext;
	m_mpNext = NULL;
}


void MorrisPratt::test()
{
	TimeIt tt;
	MorrisPratt mp;
	mp.search();
	mp.OUTPUT(tt.GetMSecElapsed());
}

void MorrisPratt::preMp(char *x, int m, int mpNext[]) 
{
   int i, j;

   i = 0;
   j = mpNext[0] = -1;
   while (i < m) {
      while (j > -1 && x[i] != x[j])
         j = mpNext[j];
      mpNext[++i] = ++j;
   }
}


void MorrisPratt::search() 
{
	char *x = (char*)m_search,
		 *y = (char*)m_context;
	int m = strlen(m_search), 
		n = strlen(m_context);

	int i, j;
   
	if (m_pNum < m) {
		delete [] m_mpNext;
		m_mpNext = new int[m+1];
		m_pNum = m;
	}

	/* Preprocessing */
	preMp(x, m, m_mpNext);

	/* Searching */
	i = j = 0;
	while (j < n) {
		while (i > -1 && x[i] != y[j])
			i = m_mpNext[i];
		i++;
		j++;
		if (i >= m) {
			OUTPUT(j - i);
			i = m_mpNext[i];
		}
	}

	delete [] m_mpNext;
	m_mpNext = NULL;
}