withdfa.cpp

来自「多种字符串匹配算法 多种字符串匹配算法」· C++ 代码 · 共 66 行

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

#include "withDFA.h"
#include <string.h>

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

withDFA::withDFA()
{}

withDFA::~withDFA()
{}


void withDFA::test()
{
	TimeIt tt;
	withDFA dfa;
	dfa.search();
	dfa.OUTPUT(tt.GetMSecElapsed());
}

void withDFA::preAut(char *x, int m, Graph* aut) 
{
	int i, state, target, oldTarget;

	for (state = aut->getInitial(), i = 0; i < m; ++i) {
		oldTarget = aut->getTarget(state, x[i]);
		target = aut->newVertex();
		aut->setTarget(state, x[i], target);
		aut->copyVertex(target, oldTarget);
		state = target;
	}
	aut->setTerminal(state);
}
 

// 2006-02-13 dx
#define ASIZE		5
 
void withDFA::search() 
{
	char *x = (char*)m_search,
		 *y = (char*)m_context;
	int m = strlen(m_search), 
		n = strlen(m_context);

	int j, state;
	Graph* aut;

	/* Preprocessing */
	aut = Graph::newAutomaton(m + 1, (m + 1)*ASIZE);
	preAut(x, m, aut);

	/* Searching */
	for (state = aut->getInitial(), j = 0; j < n; ++j) {
		state = aut->getTarget(state, y[j]);
		if (aut->isTerminal(state))
			OUTPUT(j - m + 1);
	}
}