#ifndef REPLACE_H
#define REPLACE_H
int *Next(string P)		//特征向量計(jì)算函數(shù)
{
	int m=P.size();
	int * N=new int [m];
	N[0]=0;
	for(int i=1;i<m;i++)
	{
		int k=N[i-1];
		while(k>0&&P[i]!=P[k])
			k=N[k-1];
		if(P[i]==P[k])
			N[i]=k+1;
		else
			N[i]=0;
	}
	return N;
}
int KMP_FindPat(string S,string P,int * N,int startindex)	//KMP匹配函數(shù)
{
	int LastIndex=S.size()-P.size();
	if((LastIndex-startindex)<0)
		return -1;
	int i,j=0;
	for(i=startindex;i<S.size();i++)
	{
		while(P[j]!=S[i]&&j>0)
			j=N[j-1];
		if(P[j]==S[i])
			j++;
		if(j==P.size())
			return i-j+1;
	}
	return -1;
}
void Replace()
{
	string temp1,temp2;		//temp1是目標(biāo)字符串，temp2是替換后的字符串
	cout<<"請(qǐng)輸入要替換的字符串:"<<endl;//由于getline不吃最后一個(gè)回車(chē)，所以要回車(chē)兩次
	cin.ignore();
	getline(cin,temp1);
	cout<<"請(qǐng)輸入替換后的字符串:"<<endl;
	cin.ignore();
	getline(cin,temp2);
	int *N;
	N=Next(temp1);
	for(j=v.begin();j!=v.end();++j)		//全文替換
	{
		int startindex=0,start;
		start=KMP_FindPat((*j)->s,temp1,N,startindex);
		if(start==-1)					//無(wú)需替換，直接跳過(guò)
			continue;
		(*j)->s.replace(start,temp1.size(),temp2);
	}
	cout<<"全文替換成功!"<<endl;		//全文替換成功提示
	history++;							//歷史記錄保存
	fstream fhisout("history.his",ios::app|ios::out);
	fhisout<<"將"<<temp1<<"全文替換為"<<temp2<<'\n';
	fhisout.close();
	system("pause");
}
#endif