经常某些论坛，或者软件中对某些字符串进行了关键字过滤, 一般代替为*号，一般的算法是利用strstr算法，即使是string的find子串算法复杂度也是(N*log(n))，并非kmp算法，也非bm查找子串算法。
对于一组关键字过滤，特别是对于一组字符串多，且长度不规律的字符串过滤算法完全是有必要的。
网上对于关键字过滤算法较多，且实现方法较多，本文主要介绍基于一种把关键字转换为Unicode，然后对关键字的字符或者单个关键字hash求值。算法复杂度为O(n).
对于汉字的hash值的求法，因为是Unicode编码是16位，哈希求值:
/**//// 求汉字的哈希值
long HashFun(wchar_t word)
{
BYTE l = LOBYTE(word);
int h = HIBYTE(word);
long num = h << 8 ;
num +=l;
return num;
}
基本算法思想;
1.建立2个过滤关键字数组:数组1：为单个字符 数组2：为2个或者多个字符
2.求出数组1，2的hash值，数组2的hash值只求出前2个字符的hash值即可。
3.扫描待检测的文本，然后每次取2个字符，查找数组2是否有匹配，如果没有则查找数组1。。。。 查找为O(1)
主要代码如下:
/**//*
File : WordFilter.cpp
brief: 关键字过滤程序，复杂度为O(n)，线性
Author: Expter
Data : 2009/06/30
对汉字或者字符进行哈希算法，先转换为unicode编码，然后求其hash值。
主要算法为:
1.建立2个过滤关键字数组:数组1：为单个字符 数组2：为2个或者多个字符
2.求出数组1，2的hash值，数组2的hash值只求出前2个字符的hash值即可。
3.扫描待检测的文本，然后每次取2个字符，查找数组2是否有匹配，如果没有则查找数组1。。。。 查找为O(1)
不足:
不能很好的分词。过滤不是很准确，每次只能1，2个词的过滤。
*/
#include <stdlib.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <windows.h>
#include <wchar.h>
#include <iosfwd>
using namespace std;
wchar_t des1 [5][2] = { L"汉",L"字",L"测",L"试",L"个"};
wchar_t des2 [3][5] = { L"用汉", L"的啥" ,L"测试啊"};
wchar_t src[] = { L"这个原来是打算的啥子东西用汉字只是一个是不是测试"};
/**//// 求汉字的哈希值long HashFun(wchar_t word)
{
BYTE l = LOBYTE(word);
int h = HIBYTE(word);
long num = h << 8 ;
num +=l;
return num;
}
long HashFun(wchar_t * word)
{
return HashFun(word[0])*10 + HashFun(word[1]);
}
void ParamVer(map<long,int> hashmp , wchar_t *src , int i)
{
long val = HashFun(src[i+1]);
if(hashmp[val] == 1)
{
src[i+1] = L'*';
}
}
void VmAlorgthm(map<long,int> hashmp,wchar_t *src)
{
long val = 0;
int m = wcslen(src) ;
// O(n);
for(int i = 0 ; i < m-1 ; i ++)
{
if( HashFun(src[i]) != L'*')
{
val = HashFun(src[i]) + HashFun(src[i+1]);
if( hashmp[val] == 1)
{
src[i] = L'*';
src[i+1] =L'*';
}
else
{
val = HashFun(src[i]);
if(hashmp[val] == 1)
{
src[i] = L'*';
}
else
{
ParamVer(hashmp,src,i);
}
}
}
else
{
ParamVer(hashmp,src,i+1);
}
}
ParamVer(hashmp,src,m-1);
}
int _tmain(int argc, _TCHAR* argv[])
{
wcout.imbue(locale("chs"));
typedef map<long,int> HASHMAP;
cout <<" 需要过滤文本: ";
wcout<< src <<endl;
cout <<" 过滤关键字 : " ;
for(int i = 0 ;i < 5; i++)
wcout << des1[i][0] <<" ";
wcout <<endl;
cout <<" 过滤关键词 : " ;
for(int i = 0 ;i < 3; i++)
wcout << des2[i] <<" ";
wcout <<endl;
long val = 0;
HASHMAP hash_map;
/**//// 字 hash
for(int i = 0 ; i < 5 ; i++)
{
val = HashFun(des1[i][0]);
hash_map[val] = 1;
}
/**//// 词 hash
for(int i =0 ; i < 3 ; i++)
{
val = HashFun(des2[i]);
hash_map[val] = 1;
}
VmAlorgthm(hash_map,src);
cout <<"\n-------------------------------------------------------------\n"
<<" 过滤后的文本: ";
wcout<< src <<endl;
return 0;
}