matchingstring.cpp

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

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


// check http://www-igm.univ-mlv.fr/~lecroq/string/ for the
// detail info of string searching.
#include "MatchingString.h"
#include <iostream>

const char* str1 = "Hashing provides a simple method that avoids		\
	the quadratic number of character comparisons in most		\
	practical situations, and that runs in linear time under	\
	reasonable probabilistic assumptions. It has been			\
	introduced by Harrison and later fully analyzed by Karp		\
	and Rabin.													\
	Assuming that the pattern length is no longer than the		\
	memory-word size of the machine, the Shift Or algorithm		\
	is an efficient algorithm to solve the exact				\
	string-matching problem and it adapts easily to a wide		\
	range of approximate string-matching problems.				\
	The first linear-time string-matching algorithm is from		\
	Morris and Pratt. It has been improved by Knuth, Morris		\
	and Pratt. The search behaves like a recognition process	\
	by automaton, and a character of the text is compared to	\
	a character of the pattern no more than log(m+1) ( is the	\
	golden ratio ). Hancart proved that this delay of a			\
	related algorithm discovered by Simon makes no more than	\
	1+log2m comparisons per text character. Those three			\
	algorithms perform at most 2n-1 text character comparisons	\
	in the worst case.";
const char* str2 = "algorithm";

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

MatchingString::MatchingString()
{
	m_context = str1;
	m_search = str2;
}

MatchingString::~MatchingString()
{}


//Brute force algorithm
void MatchingString::search()
{
	char *x = (char*)m_search,
		 *y = (char*)m_context;
	int m = strlen(m_search), 
		n = strlen(m_context);

	int i, j;

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

void MatchingString::OUTPUT(int i)
{
	std::cout << i << std::endl;
}