ds2_14.cpp

这是清华大学出版社的《数据结构》的电子文档讲义

// ds2_14.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "array.h"

int f1[10];

void replace(string& s,string& p,string& r){
	string temp;
	int k,remain;
	k=s.kmpFind(p, f1);
	if(k>0){
		temp=s(0,k);
		temp+=r;
		remain=s.curLen-k-p.curLen;
		temp+=s(k+p.curLen,remain);
		}
	s=temp;
	}

int main(int argc, char* argv[])
{
	string s1("student"), s2(s1), s3;		//检查构造函数
	cout<<"s1="<<s1<<endl;
	cout<<"s2="<<s2<<endl;
	s3=s1;									//检查赋值运算
	cout<<"old s3="<<s3<<endl;
	s3+=s2;									//检查连接运算
	cout<<"new s3="<<s3<<endl;

	s1="abaabcabbcabaabcabacdfghtjkl";		//目标串
	s2="abaabcaba";							//模式串
	s3="oooooo";							//替换串
	s2.calcf1(f1);							//生成前缀数组
	cout<<"f1[j]=";
	for(int i=0; i<9; i++)cout<<f1[i]<<',';	//输出
	cout<<endl<<endl;
	cout<<"old s1="<<s1<<endl;				//输出目标串
	cout<<"pat s2=          "<<s2<<endl;		//输出模式串
	replace(s1,s2,s3);						//替换
	cout<<"new s1="<<s1<<endl;					//输出替换结果
	return 0;
}