作者: panic 2005年3月11日。
简要说明：
SetFilterSpace::SetFilter是一个用来查找序列中给定 对象组合 的模板类，
首先把需要匹配的 对象组合 通过Append方法添加到类内部的树中，
然后调用TestSet方法依次检查对象序列中的每一个元素，
最后再控制台打印出查找的结果。
还可以通过Reset方法清除上次查找的结果。
这个类最初的目的是在给定的string中查找一系列keyword的位置，后来泛化成了模板类。
代码比较长，里面使用了lower_bound进行查找，被查找的对象只要拥有< 和 == 操作符，就能使用这个类。
代码的时间复杂度是O( m * log(n) ),其中m是序列的长度，n是 对象组合(关键字)的数目。
这个代码可以用来检索指定文本中的批量关键字。
不多做解释，有兴趣的朋友可以自己研究，需要对泛型编程，STL有一定的了解，否则无法理解代码中使用的各种手法。
因为代码写的很匆忙，注释很少，而且可能还会存在一定的错误，请留言说明你的问题，以便改正/改善。
有兴趣的朋友还可以把它改写成拥有查找/替换等复杂功能的模板。
源代码下载
#include <string>
#include <vector>
#include <algorithm>
#include<iostream>
using namespace std;
//written by panic,2005/3/11
namespace SetFilterSpace
{
template<class T>
class SetTree
{
public:
typedef std::vector<T> SET_VECTOR;
typedef std::vector<SetTree *> SetTreeVector;
private:
bool m_bLeaf; //是叶节点。
SetTreeVector m_Children; //子树
T m_ThisSet; //该节点的SET
SetTree * m_pParent;
public:
SetTree(T set = 0,SetTree * pParent = 0):m_ThisSet(set),m_bLeaf(false),m_pParent(pParent) {}
~SetTree()
{
SetTreeVector::iterator it;
for( it = m_Children.begin(); it != m_Children.end(); it++)
{
delete (*it);
}
}
SET_VECTOR FindRoute() const
{
SET_VECTOR r;
if( m_pParent )
{
r = m_pParent->FindRoute();
}
if( m_pParent) r.push_back(m_ThisSet);
return r;
}
void Append(SET_VECTOR::const_iterator it_begin, SET_VECTOR::const_iterator it_end)
{
SetTreeVector::iterator it;
T set;
if( it_begin != it_end )
{
set = *it_begin; //首个元素。
it_begin++;
it = std::lower_bound(m_Children.begin(),m_Children.end(),set,SetTreeOrder<T>());
if ( it != m_Children.end()) //找到位置，但是数据不一定对。
{
if(set == (*it)->m_ThisSet ) //数据对。
{
if( it_begin != it_end )
{
(*it)->Append(it_begin,it_end);
}
else
{
(*it)->m_bLeaf = true;
}
}
else
{
SetTree * p = new SetTree(set,this);
m_Children.insert(it,p);
if( it_begin != it_end )
{
p->Append(it_begin,it_end);
}
else
{
p->m_bLeaf = true;
}
}
}
else //没找到。
{
SetTree * p = new SetTree(set,this);
m_Children.insert(it,p);
if( it_begin != it_end )
{
p->Append(it_begin,it_end);
}
else
{
p->m_bLeaf = true;
}
}
}
}
SetTree * TestSet(const T &set) const
{
SetTreeVector::const_iterator it;
it = std::lower_bound(m_Children.begin(),m_Children.end(),set,SetTreeOrder<T>());
if( it != m_Children.end()) //找到位置
{
if( (*it)->m_ThisSet == set )
{
return (*it);
}
}
return 0;
}
bool IsLeaf() const { return m_bLeaf; }
bool operator < ( const SetTree & other) const { return m_ThisSet < other.m_ThisSet; }
bool operator < ( const T& other) const { return m_ThisSet < other; }
};
template<class T>
class SetTreeOrder
{
public:
bool operator ()( const SetTree<T> * pleft, const SetTree<T> * pright) const
{
return *pleft < *pright;
}
bool operator ()( const SetTree<T> * pleft, const T& right) const
{
return *pleft < right;
}
};
template<class T>
class SetFilter
{
SetTree<T> m_Tree;
SetTree<T>::SetTreeVector m_Result;
SetTree<T>::SetTreeVector m_Excute;
SetTree<T>::SetTreeVector m_SetResult;
std::vector<unsigned long> m_SetOffset;
unsigned long m_ulCount;
public:
typedef std::vector<T> SET_VECTOR;
SetFilter() : m_ulCount(0) {}
void Append(SetTree<T>::SET_VECTOR::const_iterator it_begin, SetTree<T>::SET_VECTOR::const_iterator it_end)
{
m_Tree.Append(it_begin,it_end);
}
void TestSet(T set)
{
SetTree<T>::SetTreeVector::iterator it;
SetTree<T> * p = 0;
m_ulCount++; //计算当前的偏移。
m_Excute.push_back( &m_Tree );
for( it = m_Excute.begin(); it != m_Excute.end(); it++ )
{
p = (*it)->TestSet(set);
if( p )
{
m_Result.push_back(p);
if( p->IsLeaf() )
{
m_SetResult.push_back(p);
m_SetOffset.push_back(m_ulCount);
}
}
}
m_Excute = m_Result;
m_Result.clear();
}
void ShowSetResult()
{
unsigned long i;
for(i = 0; i < m_SetResult.size(); i++ )
{
unsigned long j;
SET_VECTOR rt = m_SetResult[i]->FindRoute();
unsigned long ulOffset = m_SetOffset[i] - rt.size();
std::cout<< "Offset: " << ulOffset << " Data: " ;
for( j = 0; j < rt.size(); j++)
{
std::cout<< rt[j];
}
std::cout<< std::endl;
}
std::cout<< "总匹配数量是：" << m_SetResult.size()<< std::endl;
}
void Reset()
{
m_ulCount = 0;
m_Result.clear();
m_Excute.clear();
m_SetResult.clear();
m_SetOffset.clear();
}
};
};
using namespace SetFilterSpace;
//下面要使用的辅助函数。
char CreateRandomChar()
{
return (rand()%( 'Z' - 'A' ) + 'A' );
}
const std::string CreateRandomString(int size)
{
std::string str;
str.empty();
for( int i = 0; i < size; i++)
{
str += CreateRandomChar();
}
return str;
}
//使用方法示例：
typedef char MY_TYPE;
int test (int keycount,int keysize,int buflen,int seed)
{
SetFilter<MY_TYPE> sf;
SetFilter<MY_TYPE>::SET_VECTOR v;
MY_TYPE st = 0;
srand(seed);
cout<< "现在开始构造关键字列表" << endl;
for( int j = 0; j < keycount; j++)
{
v.clear();
for( int i = 0; i < keysize; i++)
{
st = CreateRandomChar();
v.push_back(st);
cout << st;
}
cout << endl;
sf.Append(v.begin(),v.end());
}
cout<< "现在开始构造需要搜索的缓冲区" << endl;
v.clear();
for( int i = 0; i < buflen; i++)
{
st = CreateRandomChar();
v.push_back(st);
// std::cout<< st;
}
cout<< "现在开始搜索" << endl;
for( i = 0; i < buflen; i++)
{
sf.TestSet(v[i]);
cout << v[i] ;
}
cout << endl;
cout<< "搜索结果：" << endl;
sf.ShowSetResult();
return 0;
}
int main(int argc, char* argv[])
{
int keycount = 5;
int keysize = 1;
int buflen = 50;
int seed = 4;
test(keycount,keysize,buflen,seed);
return 0;
}