数据结构与算法（Python版）第2版 课件 chap5 串

第5章串串串是由零个或多个字符组成的有限序列 s=“a1a2…an”(n

0，串长度)子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。长度：字符个数空串：string=""，长度为0空格串：stringBlank="",仅含一个空格，长度为1字串：串中任何连续字符组成主串：包含子串b的串，称为b的主串真子串：串的所有字串，除了自身以外字串的位置：子串中第一个字符的位置串相等：长度和位置相等2创建串

defCreateString(self):#创建串stringSH=input("请输入字符串：")iflen(stringSH)>self.MaxStringSize:print("溢出，超过的部分无法保存")self.chars=stringSH[:self.MaxStringSize]else:self.chars=stringSH3串连接defStringConcat(self,strSrc):#串连接lengthSrc=len(strSrc)stringSrc=strSrciflengthSrc+len(self.chars)<=self.MaxStringSize:self.chars=self.chars+stringSrcelse:print("两个字符的长度之和溢出，超过的部分无法显示")size=self.MaxStringSize-len(self.chars)self.chars=self.chars+stringSrc[:size]print("连接后字符串为：",self.chars)4取长度为length的子串defSubString(self,iPos,length):#从iPos位置开始，取长度为length的子串ifiPos>len(self.chars)-1oriPos<0orlength<1or(length+iPos)>len(self.chars):print("无法获取")else:substr=self.chars[iPos:iPos+length]print("获取的字串为：",substr)5说明：串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。

串的模式匹配算法串匹配(查找)的定义:StrInex(S,pos,T)初始条件：主串S和T存在，T是非空串并且1≤pos≤Length(S)。

操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中从第

pos个字符开始第一次出现的位置；

否则函数值为0。

一、简单匹配算法（Brute-Force）二、首尾匹配算法三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法1.简单匹配算法的思路：依次将主串S中长度和模式t相同的子串与模式进行比较，直到找到相同的子串为止。如果存在相同的子串，则匹配成功，返回子串在主串S中的位置pos。 否则匹配不成功。子串与模式的比较策略：从前到后依次进行比较。第一趟匹配ababcabcacbababcac第二趟匹配ababcabcacbababcac第三趟匹配ababcabcacbababcac第四趟匹配ababcabcacbababcac第五趟匹配ababcabcacbababcac第六趟匹配ababcabcacbababcac1.简单匹配算法的匹配实例：首尾匹配算法的思路：1)依次将主串S中长度和模式t相同的子串与模式进行比较，直到找到相同的子串为止。2)如果存在相同的子串，则匹配成功，返回子串在主串S中的位置pos。 否则匹配不成功。3)子串与模式的比较策略：先比较模式串的第一个字符,再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。

KMP为(D.E.Knuth与V.R.Pratt和J.H.Morris)同时发现的算法，因此人们称之为克努特－莫里斯－普拉特算法。

特点是在匹配的过程中，不需要回溯主串的指针i，且时间复杂度可以达到O(m+n)。3.KMP算法基本概念：前缀与后缀设A为字母表，X=x1...xn，是在A上的长度为n的一个字符串。

X的前缀(prefix)是一个子串uu

=

x1...xb|

这里

b

{1,

...,n}就是说x开始于u。

X的后缀(suffix)是一个子串uu

=

xn-b...xn|

这里

b

{1,

...,

n}就是说x结束于u。若b<n，则相应u分别称为真前缀（真后缀）

设X=abacab。X的真前缀是

,a,ab,aba,abac,abacaX的真后缀是

,b,ab,cab,acab,bacab基本概念：前缀与后缀举例第一趟匹配ababcabcacbababcac第二趟匹配ababcabcacbababcac第三趟匹配ababcabcacbababcac第四趟匹配ababcabcacbababcac第五趟匹配ababcabcacbababcac第六趟匹配ababcabcacbababcac简单匹配算法的情况：第一趟匹配第二趟匹配第三趟匹配ababcabcacbabababcabcacbabababcabcacbababcacabcac(a)bcac改进后的匹配情况：123456789123456789123456789词法分析表达式“3+4*2“看作一个字符串。通过遍历这个字符串，当遇到数字字符时，使用一个内部循环来提取完整的数字（操作数）作为一个单词存入tokens列表中；当遇到非数字字符（操作符）时，直接将其作为一个单词存入tokens列表。最终，tokens列表包含了这个表达式的所有单词，类似于编译器词法分析的结果。18字串统计字串统计:给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。输入格式第一行一个数字L。

第二行是字符串S。（L大于0，且不超过S的长度。）输出格式一行，题目要求的字符串。数据规模和约定n<=60

S中所有字符都是小写英文字母。

19串在AI中应用（1）串在自然语言处理（NLP）领域有如下应用：1)文本预处理：在NLP的几乎所有任务开始之前，都需要对文本进行预处理。串的操作在这里起到关键作用。例如，将文本分割成单词（或词素）的过程，其实就是把一个长串按照空格或其他分隔符拆分成多个子串。以句子为例，通过串的分割操作可以得到单词串。2）文本特征提取：串可以用于提取文本的一些基本特征。比如，统计某个单词（串）在一篇文档中的出现频率，这对于文本分类等任务很有帮助。将一篇新闻文章看作是一个长串，统计其中关键词的出现次数，可以作为判断文章所属领域的一个依据。3）文本相似度计算：在信息检索、问答系统等应用中，需要计算文本之间的相似度。串的比较操作可以作为基础来构建更复杂的相似度计算方法。例如，通过比较两篇文章中相同单词（串）的比例，或者使用编辑距离（一种衡量两个串差异程度的度量）来判断它们的相似程度。编辑距离是指将一个串转换成另一个串所需的最少插入、删除和替换操作的次数。例如，“kitten”和“sitting”的编辑距离是3。

20串在AI中应用（2）知识图谱构建与维护在知识