-武汉大学考题.pptx

1 1武汉大学武汉大学20002000年考题年考题算法题（本题算法题（本题12分）分）假设以假设以I和和O分别表示入栈和出栈操作，栈的初分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表态和终态均为空，入栈和出栈的操作序列可表示为仅由示为仅由I和和O组成的序列。称可以操作的序列组成的序列。称可以操作的序列为合法序列，否则称为非法序列。为合法序列，否则称为非法序列。1.下面所示的序列中哪些是合法的？下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO2.通过对问题通过对问题1的分析，写出一个算法判定给所给的操的分析，写出一个算法判定给所给的操作序列是否合法。若合法则返回作序列是否合法。若合法则返回true，否则返回，否则返回false。（假定被判定的操作序列已存入一维数组中。）（假定被判定的操作序列已存入一维数组中。）2 2#definem100#definetrue1#definefalse0int JudgeS(chars)charStackm;inttop=-1,i=0;while(si!=#)if(si=I)top+;Stacktop=si+;elseif(si=0)if(top=0)top-;i+;elsereturnfalse;elsereturntrue;3 3Essential of Lecture EightEssential of Lecture Eight:一、串的定义一、串的定义二、串类的实现二、串类的实现三、三、串的模式匹配串的模式匹配四、一些应用四、一些应用难点难点4 4一、串的定义一、串的定义string串是零个或多个字符组成的有限序列。串是零个或多个字符组成的有限序列。一般记作一般记作S=“a0a1a2an-1“(n=0)ai(0 i n-1)可以是字母、数字或其它字符；可以是字母、数字或其它字符；串的应用非常广泛，许多高级语言中都把串的作为基本串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址货物数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的每一行的名称、产地可作为字符串处理，文本文件中的每一行字符等也可作为字符串处理。串可以看成字符类型的顺字符等也可作为字符串处理。串可以看成字符类型的顺序表。序表。5 5一、串的定义一、串的定义string例：例：（1）a=“Thisisastring”（2）b=“string”（3）c=“”（4）d=“”（5）e=“你好你好”说明：说明：（1）串中包含的字符个数，称为串的长度。）串中包含的字符个数，称为串的长度。长度为长度为0的的串称为空串，它不包括任何字符串称为空串，它不包括任何字符;（2）串中所包含的字符可以是字母、数字或其他字符，）串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。这依赖于具体计算机所允许的字符集。6 6一、串的定义一、串的定义string空空串串n=0的串的串子子串串串中若干相邻字符组成的子序列串中若干相邻字符组成的子序列主主串串包含子串的串包含子串的串空格串空格串仅含有空格字符的串仅含有空格字符的串(n不为不为0)串相等串相等设设s1=a11,an1s2=a12,an2若若n1=n2且且ai1=ai2（1in1)则则s1=s2术语：术语：7 71 1voidCopy(String&copy,constStringvoidCopy(String&copy,constString&original)&original)初始条件：串初始条件：串初始条件：串初始条件：串originaloriginal已存在。已存在。已存在。已存在。操作结果：将串操作结果：将串操作结果：将串操作结果：将串originaloriginal复制得到一个串复制得到一个串复制得到一个串复制得到一个串copycopy。2 2boolEmpty()constboolEmpty()const初始条件：串已存在。初始条件：串已存在。初始条件：串已存在。初始条件：串已存在。操作结果：如串为空则返回操作结果：如串为空则返回操作结果：如串为空则返回操作结果：如串为空则返回truetrue，否则返回，否则返回，否则返回，否则返回falsefalse。3 3intLength()constintLength()const初始条件：串已存在。初始条件：串已存在。初始条件：串已存在。初始条件：串已存在。操作结果：返回串的长度，即串中的字符个数。操作结果：返回串的长度，即串中的字符个数。操作结果：返回串的长度，即串中的字符个数。操作结果：返回串的长度，即串中的字符个数。串的基本操作串的基本操作一、串的定义一、串的定义string8 84 4voidConcat(String&addTo,constvoidConcat(String&addTo,constString&addOn)String&addOn)初始条件：串初始条件：串初始条件：串初始条件：串addToaddTo和和和和addOnaddOn已存在。已存在。已存在。已存在。操作结果：将串操作结果：将串操作结果：将串操作结果：将串addOnaddOn联接到串联接到串联接到串联接到串addToaddTo的后面。的后面。的后面。的后面。5 5StringSubString(constString&s,intStringSubString(constString&s,intpos,intlen)pos,intlen)初始条件：串存在，且初始条件：串存在，且初始条件：串存在，且初始条件：串存在，且0pos0poss.Length()s.Length()，0len0lens.Length()pos+1s.Length()pos+1。操作结果：返回从第操作结果：返回从第操作结果：返回从第操作结果：返回从第pospos个字符开始长度为个字符开始长度为个字符开始长度为个字符开始长度为lenlen的子串。的子串。的子串。的子串。串的基本操作串的基本操作一、串的定义一、串的定义string9 96 6intIndex(constString&text,constintIndex(constString&text,constString&target,intpos=0)String&target,intpos=0)初始条件：串初始条件：串初始条件：串初始条件：串texttext和串和串和串和串targettarget都存在，串都存在，串都存在，串都存在，串targettarget非空，非空，非空，非空，且且且且0pos0pos text.Length()text.Length()。操作结果：返回串操作结果：返回串操作结果：返回串操作结果：返回串texttext中第中第中第中第pospos个字符后第一次出现个字符后第一次出现个字符后第一次出现个字符后第一次出现的串的串的串的串targettarget的位置。的位置。的位置。的位置。串的基本操作串的基本操作一、串的定义一、串的定义string1010原始的原始的C风格的串，容易出问题。风格的串，容易出问题。char*s;在在C+在头文件在头文件string中已含了一种安全的字中已含了一种安全的字符串实现，但由于这个库没有包含在一些较老符串实现，但由于这个库没有包含在一些较老的的C+编译器中，因此本节将设计自已的安全编译器中，因此本节将设计自已的安全的的String类，使用面向对象技术来克服类，使用面向对象技术来克服C风格风格的串中存在的问题。的串中存在的问题。二、字符串的实现二、字符串的实现1111class String class String protected:protected:/串实现的数据成员串实现的数据成员串实现的数据成员串实现的数据成员:char*strVal;char*strVal;/串值串值串值串值int length;int length;/串长串长串长串长public:public:/抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明:String();String();/构造函数构造函数构造函数构造函数 virtual String();virtual String();/析构函数析构函数析构函数析构函数String(const String&copy);String(const String&copy);/复制构造函数复制构造函数复制构造函数复制构造函数String(const char*copy);String(const char*copy);/从从从从C C风格串转换的构造函数风格串转换的构造函数风格串转换的构造函数风格串转换的构造函数串类的实现串类的实现1212String(LinkList&copy);String(LinkList&copy);/从线性表转换的构造函数从线性表转换的构造函数从线性表转换的构造函数从线性表转换的构造函数int Length()const;int Length()const;/求串长度求串长度求串长度求串长度bool Empty()const;bool Empty()const;/判断串是否为空判断串是否为空判断串是否为空判断串是否为空String&operator=(const String&copy);String&operator=(const String&copy);/赋值语句重载赋值语句重载赋值语句重载赋值语句重载const char*CStr()const;const char*CStr()const;/将串转换成将串转换成将串转换成将串转换成C C风格串风格串风格串风格串const char&String:operator(int i)const;const char&String:operator(int i)const;/重载下标运算符重载下标运算符重载下标运算符重载下标运算符;1313void Write(const String&s);void Write(const String&s);/输出串输出串输出串输出串void Concat(String&addTo,const String&addOn);void Concat(String&addTo,const String&addOn);/将串将串将串将串addOnaddOn连接到连接到连接到连接到addToaddTo串的后面串的后面串的后面串的后面void Copy(String&copy,const String&original);void Copy(String&copy,const String&original);/将串将串将串将串originaloriginal复制到串复制到串复制到串复制到串copycopyvoid Copy(String&copy,const String&original,int n);void Copy(String&copy,const String&original,int n);/将串将串将串将串originaloriginal复制复制复制复制n n个字符到串个字符到串个字符到串个字符到串copy copy int Index(const String&target,const String&pattern,int Index(const String&target,const String&pattern,int pos=0);int pos=0);/查找模式串查找模式串查找模式串查找模式串patternpattern第一次在目标串第一次在目标串第一次在目标串第一次在目标串targettarget中从第中从第中从第中从第/pos/pos个字符开始出现的位置个字符开始出现的位置个字符开始出现的位置个字符开始出现的位置String SubString(const String&s,int pos,int len);String SubString(const String&s,int pos,int len);/求串求串求串求串s s的第的第的第的第pospos个字符开始的长度为个字符开始的长度为个字符开始的长度为个字符开始的长度为lenlen的子串的子串的子串的子串串相关操作串相关操作1414bool operator=(const String&first,bool operator=(const String&first,const String&second);const String&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符=bool operator(const String&first,bool operator(const String&first,const String&second);const String&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符(const String&first,bool operator(const String&first,const String&second);const String&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符 bool operator=(const String&first,bool operator=(const String&first,const String&second);const String&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符=(const String&first,bool operator=(const String&first,const String&second);const String&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符=bool operator!=(const String&first,bool operator!=(const String&first,const String&second);const String&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符!=!=1515串构造函数串构造函数(1)(1)String:String(const char*inString)String:String(const char*inString)/操作结果：从操作结果：从操作结果：从操作结果：从C C风格串转换构造新串风格串转换构造新串风格串转换构造新串风格串转换构造新串转换构造函数转换构造函数转换构造函数转换构造函数 length=strlen(inString);length=strlen(inString);/串长串长串长串长strVal=new charlength+1;strVal=new charlength+1;/分配存储空间分配存储空间分配存储空间分配存储空间 strcpy(strVal,inString);strcpy(strVal,inString);/复制串值复制串值复制串值复制串值 1616串构造函数串构造函数(2)(2)String:String(LinkList&copy)/操作结果：从线性表转换构造新串操作结果：从线性表转换构造新串转换构造函数转换构造函数length=copy.Length();/串长串长strVal=new charlength+1;/分配存储空间分配存储空间 for(int i=0;i length;i+)/复制串值复制串值copy.GetElem(i+1,strVali);strVallength=0;/串值以串值以0结束结束1717将将C+C+串转换为串转换为C C语言串语言串const char*String:CStr()constconst char*String:CStr()const/操作结果：将串转换成操作结果：将串转换成操作结果：将串转换成操作结果：将串转换成C C风格串风格串风格串风格串 return(const char*)strVal;return(const char*)strVal;/串值类型转换串值类型转换串值类型转换串值类型转换 1818串比较实现串比较实现串比较实现串比较实现bool operator=(const String&first,bool operator=(const String&first,const String&second)const String&second)/操作结果：重载关系运算符操作结果：重载关系运算符操作结果：重载关系运算符操作结果：重载关系运算符=return strcmp(first.CStr(),second.CStr()=0;return strcmp(first.CStr(),second.CStr()=0;bool operator(const String&first,bool operator(const String&first,const String&second)const String&second)/操作结果：重载关系运算符操作结果：重载关系运算符操作结果：重载关系运算符操作结果：重载关系运算符 return strcmp(first.CStr(),second.CStr()0;return strcmp(first.CStr(),second.CStr()0;1919进一步串操作示例进一步串操作示例进一步串操作示例进一步串操作示例void Concat(String&addTo,const String&addOn)void Concat(String&addTo,const String&addOn)/操作结果：将串操作结果：将串操作结果：将串操作结果：将串addOnaddOn连接到连接到连接到连接到addToaddTo串的后面串的后面串的后面串的后面 const char*cFirst=addTo.CStr();const char*cFirst=addTo.CStr();/指向第一个串指向第一个串指向第一个串指向第一个串const char*cSecond=addOn.CStr();const char*cSecond=addOn.CStr();/指向第二个串指向第二个串指向第二个串指向第二个串char*copy=new charstrlen(cFirst)+char*copy=new charstrlen(cFirst)+strlen(cSecond)+1;strlen(cSecond)+1;/分配存储空间分配存储空间分配存储空间分配存储空间strcpy(copy,cFirst);strcpy(copy,cFirst);/复制第一个串复制第一个串复制第一个串复制第一个串strcat(copy,cSecond);strcat(copy,cSecond);/连接第二个串连接第二个串连接第二个串连接第二个串addTo=copy;addTo=copy;/串赋值串赋值串赋值串赋值delete copy;delete copy;/释放释放释放释放copycopy 2020模式匹配：模式匹配：在在T中中查查找找与与P相相同同的的子子串串第第一一次次出出现现的的位位置的过程。置的过程。Patternmatching主串也称为主串也称为目标串目标串Target子串也称为子串也称为模式串模式串Pattern应应用用：文文本本编编辑辑中中经经常常搜搜索索某某个个子子文文本本，又又如如分分子子生生物物学学中中，利利用用匹匹配配算算法法从从DNA序列中提取信息，获得其中的某种模式串。序列中提取信息，获得其中的某种模式串。三、串的模式匹配三、串的模式匹配2121三、串的模式匹配三、串的模式匹配简单模式匹配算法简单模式匹配算法2222第一趟匹配第一趟匹配ababcabcacbabi=0 p=abcacSub!=p Sub!=p 第二趟匹配第二趟匹配 ababcabcacbabi=1 p=abcac第三趟匹配第三趟匹配 ababcabcacbabi=2 p=abcacSub!=p 三、串的模式匹配三、串的模式匹配简单模式匹配算法简单模式匹配算法2323第六趟匹配第六趟匹配 ababcabcacbabi=5 p=abcac匹配成功匹配成功三、串的模式匹配三、串的模式匹配第四趟匹配第四趟匹配 ababcabcacbabi=3 p=abcacSub!=p 第五趟匹配第五趟匹配 ababcabcacbabi=4 p=abcacSub!=p Sub=p 简单模式匹配算法简单模式匹配算法2424int SimpleIndex(const String&T,const String&P,int SimpleIndex(const String&T,const String&P,int pos=0)int pos=0)/操作结果操作结果操作结果操作结果:查找模式串查找模式串查找模式串查找模式串P P第一次在目标串第一次在目标串第一次在目标串第一次在目标串T T中从第中从第中从第中从第pospos个个个个/字符开始出现的位置字符开始出现的位置字符开始出现的位置字符开始出现的位置 int i=pos,j=0;int i=pos,j=0;简单模式匹配算法简单模式匹配算法2525while(i T.Length()&j P.Length()while(i T.Length()&j P.Length()if(Ti=Pj)if(Ti=Pj)/继续比较后续字符继续比较后续字符继续比较后续字符继续比较后续字符i+;j+;i+;j+;elseelse/指针回退指针回退指针回退指针回退,重新开始新的匹配重新开始新的匹配重新开始新的匹配重新开始新的匹配i=i-j+1;j=0;i=i-j+1;j=0;if(j=P.Length()return i-j;if(j=P.Length()return i-j;/匹配成功匹配成功匹配成功匹配成功else return-1;else return-1;/匹配失败匹配失败匹配失败匹配失败 2626简单模式匹配算法简单模式匹配算法假设假设:目标串目标串T aaaaaaaaaaaa模式串模式串Paaaaab缺缺点点：每每次次都都在在比比较较到到模模式式串串的的最最后后一一个个字符时才发现不匹配。字符时才发现不匹配。改进：首尾字符串模式匹配算法改进：首尾字符串模式匹配算法但但若若不不匹匹配配出出现现在在模模式式串串的的中中间间位位置置，效效率反而会降低。率反而会降低。2727三、串的模式匹配三、串的模式匹配首尾字符串模式匹配算法首尾字符串模式匹配算法int FrontRearIndex(const String&T,const String&P,int int FrontRearIndex(const String&T,const String&P,int pos=0)pos=0)/操作结果操作结果操作结果操作结果:查找模式串查找模式串查找模式串查找模式串P P第一次在目标串第一次在目标串第一次在目标串第一次在目标串T T中从第中从第中从第中从第pospos个字个字个字个字符开始出现的位置符开始出现的位置符开始出现的位置符开始出现的位置 int startPos=pos;int startPos=pos;while(startPos T.Length()-P.Length()+1)while(startPos T.Length()-P.Length()+1)2828首尾字符串模式匹配算法首尾字符串模式匹配算法int front=0,rear=P.Length()-1int front=0,rear=P.Length()-1while(front=rear)while(front rear)return startPos;if(front rear)return startPos;/匹配成功匹配成功匹配成功匹配成功else+startPos;else+startPos;return-1;return-1;2929匹配算法分析匹配算法分析三、串的模式匹配三、串的模式匹配设设n=T.Length();m=P.Length();最好情况的复杂度为最好情况的复杂度为O(m),如如P=“STING”T=“STINGSEARCHINGEXAMPLECONSISTINGOFSIMPLETEXT”最坏情况的复杂度为最坏情况的复杂度为O(n*m),如如P=“00000001”T=“0000000000000000000000000000001”3030匹配算法分析与改进匹配算法分析与改进三、串的模式匹配三、串的模式匹配在最坏情况下，第在最坏情况下，第i趟匹配成功，前面趟匹配成功，前面i-1趟的不成功趟的不成功的匹配中，每趟比较了的匹配中，每趟比较了m次，第次，第i趟成功时也比较了趟成功时也比较了m次，所以共比较了次，所以共比较了im次。因此在最坏情况下，平均次。因此在最坏情况下，平均比较次数是：比较次数是：由于由于nm，故上述的时间复杂度为，故上述的时间复杂度为O(mn)3131简简单单匹匹配配算算法法缺缺点点在在于于每每次次不不能能匹匹配配以以后后主主串串（目目标标串串）指指针针和和子子串串（模模式式串串）指指针针都都必必须须回回溯溯，造造成成了了这种算法的时间复杂度为这种算法的时间复杂度为O(m*n)。而而KMP算算法法使使得得主主串串指指针针不不必必回回溯溯而而只只需需回回溯溯模模式式串串指指针针，并并且且模模式式串串指指针针也也不不一一定定需需要要回回溯溯到到模模式式串串的的第一个字符，第一个字符，KMP算法的时间复杂度为算法的时间复杂度为O(m+n)。例如，当：例如，当：T=“0000000000000000000000000000001”P=“000001”时，时，KMP算法算法比简单算法效率要高的多。比简单算法效率要高的多。模式匹配的改进模式匹配的改进3232改进算法是由改进算法是由D.E.Knuth,J.H.Morris,和和V.R.Pratt同时发现的。同时发现的。KMP字符串模式匹配算法字符串模式匹配算法第第1趟匹配趟匹配 T abaabab P abab|第第2趟匹配趟匹配 T abaabab P abab|第第3趟匹配趟匹配 T abaabab P abab|应该直接跳过第应该直接跳过第2趟，趟，直接进行第直接进行第3趟的趟的t3和和p1的比较。的比较。已知已知p1=t1，而，而p0p1那么那么p0t1由于由于p0=p2，所以，所以t2=p03333改进算法是由改进算法是由D.E.Knuth,J.H.Morris,和和V.R.Pratt同时发现的。同时发现的。基本思想：基本思想：abadabd?0taba0pdabcacbabapdabij匹配失败匹配失败!KMP字符串模式匹配算法字符串模式匹配算法3434比较到第比较到第i+1趟匹配时，如果比较到趟匹配时，如果比较到P中第中第j个字个字符时不匹配。即：符时不匹配。即：tpi+jtiti+1.ti+j-1jp0p1.pj-1第第i+1趟趟ti+jpjtpti+1ti+2.ti+jti+mp0p1.pj-1pm-1第第i+2趟趟若匹配成功若匹配成功3535tpi+jtiti+1.ti+j-1jp0p1.pj-1第第i+1趟趟ti+jpjpp0p1.pj-2p1p2.pj-1p假设假设ti+1ti+2.ti+j-1由此，第由此，第i+2趟匹配可以跳过不做。趟匹配可以跳过不做。仅考察仅考察模式串模式串3636第第i+3趟匹配是否需要进行呢？趟匹配是否需要进行呢？tpi+jtiti+1.ti+j-1jp0p1.pj-1第第i+1趟趟ti+jpj假设假设模式串模式串pp0p1.pj-3p2p3.pj-1p假设假设ti+2ti+3.ti+j-1由此，第由此，第i+3趟匹配可以跳过不做。趟匹配可以跳过不做。3737依此类推，直到对于某值依此类推，直到对于某值k，使得，使得p0p1.pkpj-k-1pj-kpj-1而而p0p1.pk-1=pj-kpj-k+1pj-1ti+jtiti+1.ti+j-1pp0p1.pkk+1jpj-k-1pj-k.pj-1p0p1.pk-1pj-kpj-k+1.pj-1=pki+j3838假设主串为：假设主串为：t0t1.tn-1模式串为：模式串为：p0p1.pm-1我我们们要要解解决决的的问问题题是是：当当“失失配配”(ti pj)时时，模模式式串串“向向右右滑滑动动”的的可可行行距距离离有有多多远远；或或者者说说，下下一一步步ti应应该与模式串中的哪个字符比较该与模式串中的哪个字符比较?可以推断：答案将完全取决于模式串，而与主串无关可以推断：答案将完全取决于模式串，而与主串无关因因此此：可可以以预预先先为为模模式式串串设设定定一一个个数数组组nextj，当当“失配失配”(ti pj)时，时，i不变，不变，j改为改为nextj。KMP字符串模式匹配算法字符串模式匹配算法3939定义定义定义定义nextjnextj如下：如下：如下：如下：例：例：例：例：j j 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 模式串模式串nextjnextj a b a a b c a c a b a a b c a c-1 0 0 1 1 2 0 1-1 0 0 1 1 2 0 1nextj=Maxk|0kj且且P0Pk-1=Pj-kPj-k+1Pj-1当此集合不空时当此集合不空时0其他情况其他情况-1当当j=0时时KMP字符串模式匹配算法字符串模式匹配算法4040intKMPIndexHelp(constString&T,constString&P,intpos,intnext)inti=pos,j=0;while(iT.Length()&jP.Length()if(j=-1)i+;j=0;elseif(Pj=Ti)i+;j+;elsej=nextj;if(js;/读入字符串读入字符串i=0;j=0;k=0;while(si)/改造字符串改造字符串if(i%2=1)stkk+=si;elsesj+=si;i+;while(i0)sj+=stk-k/将第偶数个字符填入原将第偶数个字符填入原字符数组字符数组4848如果字符串的一个串（其长度大于如果字符串的一个串（其长度大于1）的各个字符均）的各个字符均相等，则称之为等值子串。试设计一个算法：输入字符相等，则称之为等值子串。试设计一个算法：输入字符串串S，以，以#作为结束标记，如果串作为结束标记，如果串S中不存在等值子中不存在等值子串，则输出信息：串，则输出信息：“无等值子串无等值子串”，否则求出（输出），否则求出（输出）一个长度最大的等值子串。一个长度最大的等值子串。例如：例如：s=”xyz123xyz123#”，则输出：无等值子串；，则输出：无等值子串；又如：若又如：若s=”xyzyyzxxxmmmmmzzzyy#”，则输出，则输出等值子串等值子串:mmmmm实战实战2:4949分析：此题主要考察字符串的查找操作。在查找分析：此题主要考察字符串的查找操作。在查找过程中，对等值字符进行统计，由于字符串以过程中，对等值字符进行统计，由于字符串以#作作为结束标记，则无须通过字符串的长度来判断字符是否为结束标记，则无须通过字符串的长度来判断字符是否遍历结束。求主串中最长的重复子串，该算法同样适用。遍历结束。求主串中最长的重复子串，该算法同样适用。实战实战2:5050voidMaxEqSubstr(String&s,String&t)intmax=0,index=0;/index记最长的串在记最长的串在s串中的开串中的开始位置，始位置，max记其长度记其长度inti=0,start=0,length=1;/length记局部重复子串长度记局部重复子串长度intn=s.Length();while(in-1)if(si=si+1)length+;i+;continue;else if(maxlength)index=start;/起始位置起始位置max=length;/长度长度i+;start=i;length=1;t=SubString(s,index,max);/求子串函数求子串函数5151实战实战3:m个苹果放到个苹果放到n个盘子上个盘子上(允许有空盘允许有空盘子子)，问有多少种放法，问有多少种放法?递归出口：递归出口：没有苹果或者盘子剩下没有苹果或者盘子剩下1个：个：1种种苹果数少于盘子数：苹果数少于盘子数：去掉多余的盘子去掉多余的盘子苹果数多于盘子数苹果数多于盘子数:至少有一个盘子空着至少有一个盘子空着和和所有的盘子都有苹果所有的盘子都有苹果(从每个盘子拿走从每个盘子拿走一个苹果一个苹果)5252实战实战3:以下是该函数的程序段，请补充完整。以下是该函数的程序段，请补充完整。intf(intm,intn)if(m=0|n=1)return;/没有苹果或者盘子剩下没有苹果或者盘子剩下1个个if(mn)return;/苹果数少于盘子数，只需要相同的盘子数苹果数少于盘子数，只需要相同的盘子数就足够了就足够了returnf(m,n-1)+f(m-n,);/苹果数多于盘子数苹果数多于盘子数5353实战实战3:以下是该函数的程序段，请补充完整。以下是该函数的程序段，请补充完整。intf(intm,intn)if(m=0|n=1)return1;/没有苹果或者盘子剩下没有苹果或者盘子剩下1个个if(mn)returnf(m,m);/苹果数少于盘子数，只需要相同的盘子数苹果数少于盘子数，只需要相同的盘子数就足够了就足够了returnf(m,n-1)+f(m-n,n);/苹果数多于盘子数苹果数多于盘子数5454本本 讲讲 小小 结结重点：重点：1、串的基本概念、串的基本概念2、串类的实现、串类的实现难点：难点：1、串的模式匹配、串的模式匹配2、串的应用、串的应用