//#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?			for（int?j?=?0;?j?			{
				if（hash[i][j]?>=?0）
				{
					fout?<