第4章串教学要求：1、掌握：串的基本概念、串的抽象数据类型、串的2种存储结构，尤其是在顺序存储下的顺序串类及其基本运算、基于穷举法的Brute-Force串的简单模式匹配算法。2、理解：KMP模式匹配算法。内容提要引子串的基本概念（串的）长度：串中字符的个数称为串的长度；空串：长度为零的串称为空串；子串：串中任意个连续的字符组成的子序列称为该串的子串。相应地包含子串的串称为主串。（字符在串中的）位置：一个字符在串这个字符序列中的序号；（子串在串中的）位置：子串的第一个字符在串中的位置。4.1串的抽象数据类型Insert(s,pos,t)：将字符串t插入到字符串s的第pos个字符前面Delete(s,pos,len)：删除字符串s的从pos起以后的len个字符SubString(s,start,len)：返回从串s的第start个字符起长度为len的字符序列（子串）Concat(s,t)：把串t拼接在串s后面模式匹配Index(s,t)：求子串t在字符串s中的位置。简单模式匹配(Brute-Force)KMP模式匹配复习：C++中的字符串函数一、串的顺序存储结构：用一组地址连续的存储单元存储串的字符序列。1、静态数组结构：constintMaxSize=100;charstr[MaxSize];2、使用动态数组：char*str;intMaxSize;str=newchar[MaxSize])3、串赋值输入一行字符串：cin.getline(str,MaxSize);利用循环输入字符串：for(inti=0;i<MaxSize;i++)cin.get(str[i]);4、串输出:cout<<str;//注意是否有串结束符二、串的链式存储结构：1.用一个链表存放字符串，每个结点只存一个字符(图示)structNode{chardata;Node*next;};Node*head;二、串的链式存储结构：2.用一个链表存放字符串，每个结点存放多个字符(图示)structNode{chardata[4];Node*next;};Node*head;4.3顺序串类StringSubStr(intpos,intlength);//求子串//在字符串对象的第pos个字符之前插入字符串svoidInsert(constString&s,intpos);//从字符串对象的pos位置开始删除以后length个字符voidDelete(intpos,intlength);/*从字符串对象的start位置开始查找字符ch，如果查找成功则返回成功位置,否则返回0*/intFind(charch,intstart);/*从字符串对象的start位置开始查找子串t，如果查找成功则返回成功位置,否则返回0*/intFind(constString&t,intstart);intLength();//以下是运算符重载charoperator[](intn);Stringoperator=(constString&s);Stringoperator=(char*s);Stringoperator+(constString&s);Stringoperator+(char*s);friendStringoperator+(char*s,constString&t);//想想为什么用友元运算符重载？？booloperator==(constString&s);booloperator==(char*s);friendbooloperator==(char*s,constString&t);booloperator!=(constString&s);booloperator!=(char*s);…….//以下是运算符重载friendostream&operator<<(ostream&,constString&s);friendistream&operator>>(istream&,constString&s);};//构造函数String::String(){str=newchar[1];str[0]='\0';size=0;}String::String(intlength){size=length;str=newchar[size+1];for(inti=0;i<size;i++)str[i]='';str[size]='\0';}//拷贝构造函数String::String(constString&s){size=s.size;str=newchar[size+1];for(inti=0;i<=size