08.第08节课第4章串

罗泽兵 · 发表于 2024-4-15 09:16:48

接下来我们再看一下substrate。恰星符号sub恰星sinter poss inter lens那么恰？星pinter k认识等于string认识s。if pose小，position小于零，或者呢，position大于s length- 1。或者任小于零，或者任大于。s length-position，那么就error。message那么参数不合法，然后返回一个错误信息。我接下来sub。等于new char。

愣是加一为我们的sub呢，分配存储空间。p=s+pose- 1k等于嫩。yok.星号SAP，加加。等于。星号p加加t减减。最后呢，星号s等于我们的反斜杠零。sub呢，等于sub减论。那么，这是我们substring？这样一个。

用sub呢，返回串s的d position的字符起始长度呢，为嫩的这样一个词串，那么我们来看一下这个部分。那么首先呢，这里是in TK。s lens等于我们这样一个string lens s等于我们字符串的这样一个长度，那么if呢？position小于零，如果比零小或者position大于SN。s认识简易，如果你这个如果比这个大的话。比这个字符串长度大的话。如果比这个字符串呢，那么它在我们这样一个。

如果比字符串，如果比我们字符串。它的这样一个。存放最后一个元素呢，它在的这样一个位置呢。要大的话，那么就是说我们这个长度的减一要大的话。或者说任小于零，或者说任呢大于我们任呢减position，我们就是说大于我们的长度呢？减去position这样一个位置，这样一个部分，我们返回一个错误信息参数不合法。接下来sub=6恰嫩加一，那么为sub呢？

分配对空间。apprehension.position+1个p=s+position- 1。那么等于我们的这样一个。这样一个串的地首，串的首地址呢？加上我们这样一个位置。那么再来减一。那么k=len。yok.星号sub加加等于星号p加加，那么接下来呢，把我们的p呢？这样一个值呢？付给。

它字符字符字符串的这样一个。字符呢，赋给我们的sub。这个数组当中。然后呢k减减，然后k-k减少一。那么直到呢我们。将我们这样一个棱长度的，这样一个字符串呢？将它覆盖了我们的。sub，那么最后呢？星号sub等于反七幺零，那么加上一个。把七二零这个字符那么作为表示结束，

最后呢？sub=sub减论。那么，将sharp的地址呢？那么，把它设置成为那么下部减震，那么这样一个长度的，这样一个。需要的我们。取得的这样一个长度的这样一个数值，这样一个部分，那么这个是我们substrate，那么用我们的sub返回s的depression格字符集。长度为嫩的这样一个字符串，它的这样一个方式。

那么，接下来最后呢？我们来看一下串的块链。存储表示。那么我们也可以用链表来存储串值，由于串的数据元素呢，是一个字符，它只有八位二进制数。因此，用链表存储时啊，通常一个节点中存放的不是一个字符，而是一个子串，那么存储密度呢？等于数据元素所占的存储位。除以实际分配的存储位，

那么我们来看一下这个块链进行定义。井井号define。tracks age 80 type deep track track。ch.char ch.track size.struct创新list。truck hyper defy street ruck head toe.int.colon mr street.那么，我们数据呢？定义我们的一个结构体结定义了我们一个结构体类型啊，接下来呢？定义了我们快变。

串的链表结构，串的头指针和尾指针，以及呢，串的当前长度。那么我们看一下这个部分。那么，我们的头指针呢？那么，指向这样一个串的部分？那么以及呢？我们的这样一个维指针，那么最后呢？我们的这样一个串的长度呢？那么是我们这样一个数值的，这样一个部分。

在实际应用时呢，可以根据问题所需来设置节点的大小。比如说在编辑系统中，整个文本编辑区呢，可以看成一个串每一行呢，是一个子串构成一个节点，比如说同一行的串定义。进场结构呢？行和行之间的指针呢？相连接。接下来我们看一下模式匹配，那么先前呢，我们介绍过串。匹配的操作。index ST position.

使用串的有关操作呢，实现了index，那么但是呢，还是可以改进的，这样一个使用的这样一个方式。我们子串的定位呢，通常称为串的模式匹配，或者说串匹配。这样一个运算呢，它的应用呢，非常广泛，比如说在搜索引擎。拼写检查。语言翻译，数据压缩等应用中都需要进行串匹配。

串的模式匹配呢，设置两个字符，串s和t设s为主，串也称为正文，串t为子，串称为模式。在主串s中，查找与模式t相匹配的子串，如果匹配成功，确定相匹配的子串呢？中的第一个字符在主串s中确定的位置，出现的位置。那么，我们的匹配算法呢？我们来看一下这些匹配的算法，

比如说int index。s dream ss dreamt interpose返回子串t呢，在主串s中depletion的字符号的位置。如果不存在，则返回值零，其中呢？t非空零小于position，小于s就是lengths。首先呢，I=post position，那么把position的值啊，那么赋给I，那么j=0。while.si+g。

不等于。我们的反斜杠零这样一个字符，并且呢TG。不等于返修杠零那么这样一个字符，那么如果我们的。si+s的这样一个字符串，这样一个字符串。那么，它这样一个。在它之后，这样一个。位置的这样一个。部分呢，之后的这样一个部分呢，没没有结束，

没有结束，并且呢TG用来。用来比较的这样一用来比。比较是否与之相等的这样一个字符串呢？它也没有结束，那么if si+g=t gg加加。那么就是说我们ssi+g。等于stg那么g加加。那么继续比较了后继的，如果这两个字符相等的话，那么我们继续比较了后继的字符。else I加，加g=0，那么如果呢？没有不相等的话。

那么我们呢？就让I+1。g=0。if TG不等于零反斜杠，0 return I。else return负一。那么，我们来看一下这个程序。首先呢s。I+g不等于反直杠零，并且呢，TG不等于反直杠零，当它们呢，没有到结束的时候。那么s呢？

I+g就是我们这样一个位置啦。这样进行比较的这个位置之后呢，那么后面的这样一个元素。开始比较了，后面的这样一个开始比较了位置之后呢，这第几个元素的部分。第几个数字符的部分呢？与我们。要比较与之与它是否相等的这样一个字，符串的后看这样一个第几个第几个字符的这样一个部分呢？是否相？依次来进行比较的这样一个部分呢，是否相是否相等是否相等，那么是否呢相等的这样一个部分？如果相等了，

就g加加继续比较后期的字符，如果相等了，就继续比较后期的字符，那么相等了，那么就。运行的这样一个比较的部分l死了I加加g=0，那么如果呢？I如果不相等的话。那么我们就让这样一个比较的位置啊，从我们的这样一个主串中那么进行移动，这样一个方式，然后重新呢开始新一轮的这样一个匹配。那么if TG。不等于反斜杠零那么retire I那么这是我们的这样一个比较字符串的这样一个方式。而这是我们的进行返回子串p，

在主串s中deportation的位置后，字符后的位置的这样一个程序的这样一个部分。那么，接下来我们看一下，那么这样一些内容，如果找到s中所有模式，所有和模式串t匹配的子串。那么，只需要多次调用index？s strings s string t imports interposition匹配成功后呢？下一次匹配开始的位置呢？就是I+strings t。那么，我们来看一下。为什么简单匹配算法？

它的性能低，因为呢，在每趟匹配不成功时，存在大量回溯，没有利用已经部分匹配的结果。那么，如果在匹配不成功时，主串不回输了，那么主串不回输模式呢？就需要向右滑动一段距离，那么我们来再看一下。k mp算法。k mp算法呢，是有这样一些。人员呢？

那么提提出了这样一个算法，那么简称k mp算法，该串该算法呢？较简单算法呢？有了较大的改进。主要是消除了主串指针的回溯，从而使。算法效益呢，进行了提高。那么，我们来看一下。k mp算法。模式匹配算法的部分，比如说我们进行匹配。那么，

我们第一套匹配呢？模式。子串第一个位置，第一个元素呢？第一个字符呢？和第二个字符呢？与我们主串相同。但是呢，第三个位置呢，就不相同。我们来看一下，再匹配的时候呢，我们向右滑动一个位置，那么它是不相同的。我们再来看一下。

第一套。第一个位置呢，和第二个位置相同，第三个位置不相同，那么我们向右滑动两个位置了，那么它是相同的。那么我们再看一下。相同第二套滑动两个位滑动两个位置啊。滑动两个滑动两个位置，滑动两个单位呢？那么，第五个位置呢？又不相同。那么，我们再向右滑动一个单位，

那么又是不相同的。那么，我们滑动两个位置呢？也是不相同的。啊，这是滑动的位置啦，不相同。然后我们再看一下。我们向右如果滑动四个位置的话。滑动三个位置的话，那么这个时候呢？那么它是相同的，那么可以呢？那么进行匹配？我们来看一下。

部分匹配时啊，有两个特征。比如说模式滑动到dk一个字符，有字有字串t1。到tk- 1。等于si-k+1。到我们的si- 1。那么就是子川的这些部分呢？等于。主串的这样一些部分，那观察适配的时候呢？那么子串的这些位置呢？也与主串的这些位置相等，那么我们年龄这两个式子呢？可以得到子串的这样一个位置呢，

等于主串那么后面的这样一些指向它。进行某个元字符进行比较的时候呢，这个这个指向的这个这个字符呢？它的位置啊？它之前它之前的这样一些。字字符呢？它有相等的部分。那么k与I呢？具有函数关系，由当前适配位置j可以计算出滑动位置k那么比较新的起点。那么，滑动位置k呢？仅与模式t有关，那么ti=tk- 1，那么经过第I位第一位呢？

往右移动。k- 1位tg-k+1到tg- 1，它就是从ig- 1位往左经过k位。那么，模式应该向右滑动多远才是最高效率的了？那么，就k=max k1-k小一小于k小于g。且t1呢，到t- 1到等于tg-t+1到tt- 1。那么，我们来看一下这个部分令k呢？等于next g那么g那么则呢？当g等于？零一时那么不进行比较，那么那个时期等于零。

g等于那个是g=1的时候g呢？七当k1小于k，小于g取t1到tk- 1=tk- 1。加一到我们的tg- 1了，这个时候呢？那么等于我们的k那么其他情况呢？等于一。那么，模式中相同的部分越多，相似的部分越多，则类似g的函数越大。它既表示模式t与字符之间的相关相关度越高。模式串向右滑动的越远与主串呢，进行比较的次数越少，时间复杂度就越低。

好吧，我们来看一下。计算机类似的g的方法当g=1的时候呢，类似的g=0那么类似的g=0呢，表示不进行比较。当g大于一的时候呢，那个时啊g的值呢，为模式串的位置，从一到g- 1构成的串中所出现的与首尾相同的子串的最大长度。当无首尾相同的子串的时候呢，那个值接的值为一那个值值接为一呢，表示从串开头。不头部开始进行字符的比较。那么，我们来看一下这个部分，

那么设目标串了是这样一个部分模式，串了是这样一个部分s，当前值为17t的值为八，用指针I表示。目标串s当前比较的字符位置。用指针ig表示，模式t当前的比较字符位置，那么k mp的模式匹配了，那么我们可以进行了。这样的比较的方式。来吧，我们首先来看一下这个表。当g=1的时候呢，那个是g=0，当g=2的时候呢，

那个是g=1，当g=3的时候呢，那个是g=1，那么后面呢是四五六七八，那么就是我们的二二三一。一二那么我们看一下。第一套模式串目标串。那么g呢？指向第二个的时候呢，等于二的时候，那个是二=1，那么第二趟。j=1的时候呢next 1=0，那么第三趟j=6的时候呢？那么next 6呢？

等于三。那么第四套。那么就是这样一个位置，那么就可以进行匹配了。那么我们看一下这个六，那个是六=3呢，表示我们进行匹配的时候呢，我们呢可以呢，从后面。从后面这个位置呢，进行比较。那么，从后面的这样一个位置来进行比较的这样一个方式，那么我们看一下k mp算法。index ctrl s区分t internet max max size I=0，

j=0 v get index get next t next。yi小于s认识。SSL并且呢，s小于tslefg=0或者s data I=t da taj。那么就加g+I加加g加加，那么ig的个增1 else g=next g，那么I不变的接后退，if g大于t。s认s和v=i-ts认s返回与匹配模式串的首下标字符，那么else呢？未等于零返回不匹配的标志，最后呢？return way。那么我们再看一下正文编辑串操作的应用比例，那么我们的WPS呢？

word呢？都是常用到的正文编辑工具，可以完成查找删除插入和修改的这样一个方式。整个文本呢，可以作为一个正文串，每行作为一个子串文本的基本操作呢，可由字符串的操作来实现，为了方便确定操作的位置呢，对正文的每一行建立一种索引信息。称为行表，比如说我们一个原程序文件正文为。float AB max+af百分f百分f取一的地址，取b的地址，那么if a大于b max=a。else max=b那么以字符串的形式呢？

来配合进行存储。在行内插入或删除若干字符的时候呢，如果没有超过行表中，该行的长度则修改正文的存储区和行表。如果超出分配给该行的存储空间，则需要为该行重新分配正文串的存储空间，并修改该表。如果要插入或删除整行呢？需要对行表进行相应的插入或删除。好同学们，今天呢，我们为大家讲了串的这样一个部分，包括了串的这样一个类型，它的存储方式，它的类型定义以及呢，

它的运算以及它的基本操作。那么大家呢，要了解串的这样一个基本操作，以及呢，我们的k mp匹模式匹配算法的这样一个部分好，大家下来的时候呢，再看一下这些部分进行一个了解和熟悉。好，我们今天的课呢，就讲到这里，谢谢大家。

		自动登录	找回密码
密码			立即注册