KMP中文字符匹配算法的C++实现

KMP中文字符匹配算法的C++实现

//#include
#include
#include 
#include
#include
#include
#include

using namespace std;

const int s1 = 0XB0s2 = 0XA1e1 = 0XF8e2 = 0XFF;
const int maxwordlen = 50;

struct Second
{
	string key;
	Second *next;
	Second（string k = ““Second *n = 0）:key（k）next（n）{}
};

struct Head
{
	int size;
	string key;
	vector W;
	Head（string k = ““int s = 0）:key（k）size（s）{}
};


void get_nextval（const char *T int next[]）
{
       // 求模式串T的next函数值并存入数组 next。
       int j = 0 k = -1;
       next[0] = -1;
      while （ T[j/*+1*/] != ‘\0‘ ）
       {
              if （k == -1 || T[j] == T[k]）
             {
                     ++j; ++k;
                     if （T[j]!=T[k]）
                            next[j] = k;
                     else
                            next[j] = next[k];
              }// if
              else
                     k = next[k];
       }// while
    ////这里是我加的显示部分
   // for（int  i=0;i       //{
       //     cout<       //}
       //cout<}


//下面是KMP模式匹配程序，各位可以用他验证。记得加入上面的函数
int KMP（const char *Textconst char* Pattern） //const 表示函数内部不会改变这个参数的值。
{
       if（ !Text||!Pattern||  Pattern[0]==‘\0‘  ||  Text[0]==‘\0‘ ）//
              return -1;//空指针或空串，返回-1。
       int len=0;
       const char * c=Pattern;
       while（*c++!=‘\0‘）//移动指针比移动下标快。
       {    
              ++len;//字符串长度。
       }
       int *next=new int[len+1];
       get_nextval（Patternnext）;//求Pattern的next函数值
   
       int index=0i=0j=0;
       while（Text[i]!=‘\0‘  && Pattern[j]!=‘\0‘ ）
       {
              if（Text[i]== Pattern[j]）
              {
                     ++i;// 继续比较后继字符
                     ++j;
              }
              else
              {
                     index += j-next[j];
                     if（next[j]!=-1）
                            j=next[j];// 模式串向右移动
                     else
                     {
                            j=0;
                            ++i;
                     }
              }
       }//while
   
       delete []next;
       if（Pattern[j]==‘\0‘）
              return index;// 匹配成功
       else
              return -1;      
}


//Dictiory类为中文分词，此处未用到，只是因项目需求就做了下，大家若有需要可以参考。
class Dictiory
{
	vector H;
	ifstream fin;
	ifstream fcin;
	ofstream fout;
	int hash[e1 - s1][e2 - s2];	
	int BinarySearch（string strint k）;
	int GetNum（）;	
	void LoadDic（）;
	bool IsC（char c）;
	bool IsEc（char c）;
	void AddWord（string strint k）;
	void InsertWord（string strint k）;	
	bool IsWord（string strint kint t）;	
	void SkipNotChinese（string &strstack &stk）;
public:
	Dictiory（string sfilenamestring dfilename）;
	void SegmentWord（string s）;
	void PrintDic（）
	{
		for（int i = 0; i < e1 - s1;i++）
			for（int j = 0; j < e2 - s2;j++）
			{
				if（hash[i][j] >= 0）
				{
					fout << H[hash[i][j]].key << en

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        170  2015-01-29 10:49  使用说明.txt

     文件        320  2015-01-25 15:35  fuzzyMatch\bookStack.txt

     文件      11674  2015-01-29 10:43  fuzzyMatch\Debug\BuildLog.htm

     文件     498688  2015-01-29 10:43  fuzzyMatch\Debug\fuzzySearch.exe

     文件        406  2015-01-29 10:43  fuzzyMatch\Debug\fuzzySearch.exe.embed.manifest

     文件        472  2015-01-29 10:43  fuzzyMatch\Debug\fuzzySearch.exe.embed.manifest.res

     文件        381  2015-01-29 10:43  fuzzyMatch\Debug\fuzzySearch.exe.intermediate.manifest

     文件     843204  2015-01-29 10:43  fuzzyMatch\Debug\fuzzySearch.ilk

     文件     816948  2015-01-29 10:43  fuzzyMatch\Debug\fuzzySearch.obj

     文件    2739200  2015-01-29 10:43  fuzzyMatch\Debug\fuzzySearch.pdb

     文件         65  2015-01-29 10:43  fuzzyMatch\Debug\mt.dep

     文件      91136  2015-01-25 15:33  fuzzyMatch\Debug\vc60.idb

     文件     151552  2015-01-25 15:30  fuzzyMatch\Debug\vc60.pdb

     文件     183296  2015-01-29 10:43  fuzzyMatch\Debug\vc90.idb

     文件     241664  2015-01-29 10:43  fuzzyMatch\Debug\vc90.pdb

     文件     784295  2008-10-24 21:50  fuzzyMatch\dictiory.txt

     文件       9319  2015-01-29 10:55  fuzzyMatch\fuzzySearch.cpp

     文件       3461  2015-01-24 14:52  fuzzyMatch\fuzzySearch.dsp

     文件        528  2015-01-24 17:34  fuzzyMatch\fuzzySearch.dsw

     文件    2444288  2015-01-29 10:55  fuzzyMatch\fuzzySearch.ncb

     文件      48640  2015-01-25 00:52  fuzzyMatch\fuzzySearch.opt

     文件       7536  2015-01-25 15:30  fuzzyMatch\fuzzySearch.plg

     文件        887  2015-01-29 10:43  fuzzyMatch\fuzzySearch.sln

    ..A..H.      8192  2015-01-29 10:55  fuzzyMatch\fuzzySearch.suo

     文件       4901  2015-01-29 10:43  fuzzyMatch\fuzzySearch.vcproj

     文件       1427  2015-01-29 10:55  fuzzyMatch\fuzzySearch.vcproj.2012-20141127ES.Administrator.user

     文件         22  2015-01-29 10:44  fuzzyMatch\resOfdivid.txt

     文件          0  2015-01-29 10:44  fuzzyMatch\result.txt

     文件         14  2015-01-29 10:44  fuzzyMatch\searchFor.txt

     文件         16  2015-01-25 11:05  fuzzyMatch\sou.txt

............此处省略5个文件信息