崇明建设镇乡镇府网站,怎么登录甘肃省建设厅网站,湛江海田网站建设招聘,wordpress自定义文章类型如何调用提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、串的定义二、串的存储结构1.顺序结构2.链式结构 三、串的朴素的模式匹配算法#xff08;暴力匹配算法#xff09;1.背景2.假设我们要从下面的主串 S文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、串的定义二、串的存储结构1.顺序结构2.链式结构 三、串的朴素的模式匹配算法暴力匹配算法1.背景2.假设我们要从下面的主串 Sgoodgoogle 中找到 Tgoogle”这个子串的位置。 四、升级版的匹配算法KMP模式匹配算法1.背景如果主串 Saabaabaaf 要匹配的子串为 T“aabaaf” 。2.KMP算法解决的问题字符串匹配中将时间复杂度从Om*n缩短到Omn3.浅显的KMP匹配过程4.关键在于如何得知让子串跳到哪个位置去跟主串比较呢这里是b——求最长相等前后缀①一个串的前缀和后缀是什么②子串为 T“aabaaf” 的前缀和后缀是什么③什么叫最长相等前后缀④根据前缀表求匹配⑤next数组是什么⑥KMP算法的思想不难难的是如何计算最长相同前后缀和next数组。 五、 KMP算法再举一个例子主串ababbaabbaababaaacb子串ababaa1手算求next数组求子串每个字母和前面一坨的最长公共前后缀长度(2)KMP过程 六、KMP算法的代码实现1.求next数组2.KMP算法 前言
关于串首先想到的就是字符串。为什么会有字符串这个东西产生呢 比如外国人说英语都是字母但是我们中国人说的话不是字母只能是汉字所以汉字这种特殊的、无法被计算机直接阅读的字符在组成一个短语或者句子时就形成了字符串。 字符串的产生是为了能够表示和处理文本信息。在计算机科学中文本是一种非常常见的数据类型例如输入的命令、输出的结果、存储的文件内容等等。为了能够对文本进行操作和处理就需要一种能够表示和存储文本的数据类型于是字符串应运而生。
字符串可以看作是由字符组成的序列每个字符都有自己的编码表示例如ASCII码或Unicode码。通过将字符依次排列组合就可以构成一个完整的字符串。字符串可以进行各种操作例如连接、截取、替换、查找等等使得对文本的处理变得更加灵活和方便。
另外字符串还可以用来表示和处理其他类型的数据例如将数字转换为字符串进行输出、从用户输入的字符串中解析出数字等等。字符串的产生也是为了满足对不同类型数据的统一处理需求。
一、串的定义
在C语言中字符和字符串是两个不同的概念但它们之间存在一些联系和关联。
字符字符是C语言中最基本的数据类型之一用于表示单个字符。它使用单引号括起来例如 ‘A’、‘9’、!等。每个字符在内存中占用一个字节的空间。
字符串字符串是由一系列字符组成的序列以空字符 ‘\0’ 结尾。在C语言中字符串实际上是以字符数组的形式存在的。例如“Hello” 可以表示为一个包含6个字符的字符数组{‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’}。字符串可以使用双引号括起来例如 “Hello”。
在数据结构中串String是由零个或多个字符组成的有限序列。它是一种线性数据结构可以用来表示和处理文本、符号序列等信息。
串的定义可以表示为一个串S是一个字符的有限序列记作S “a1a2…an”其中每个字符ai属于一个字符集n表示串的长度。串的长度可以是零称为空串。
串在存储上通常使用字符数组来表示其中每个字符占用一个存储位置。通常字符串的最后一个位置用特殊字符 ‘\0’ 表示串的结束。
二、串的存储结构
1.顺序结构
串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。 既然是定长数组就存在一个预定义的最大串长度一般可以将实际的串长度值保存在数组的0下标位置,有的书中也会定义存储在数组的最后一个下标位置。但也有些编程语言不想这么干觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符比如“\0”来表示串值的终结。 对于串数组的长度MaxSize由于串数组长度是提前给定的所以也很可能发生超出上限的情况。
2.链式结构 三、串的朴素的模式匹配算法暴力匹配算法
1.背景
字符串一般是一个有很多字符的组合比如“Ilikeappleandyou或者古诗“床前明月光疑是地上霜”这个时候我想在一个很大的字符串里面找到指定的子串“and”或者“明月”应该怎么做呢 这种子串的定位操作通常称做串的模式匹配 应该算是串中最重要的操作之一。
2.假设我们要从下面的主串 S“goodgoogle” 中找到 Tgoogle”这个子串的位置。 代码思路设主串str子串substr。先计算出两个字符串的长度为10和6大循环从0开始循环 str_len - substr_len4次表示子串最多后移四次就无法匹配成功了。每一次大循环里面让子串的每一位和主串对应位比较如果不相等就跳出小循环大循环让子串后移一位。
int findSubstring(char *str, char *substr) {int str_len strlen(str);int substr_len strlen(substr);for (int i 0; i str_len - substr_len; i) {int j;for (j 0; j substr_len; j) {if (str[i j] ! substr[j]) {break;}}if (j substr_len) {return i; // 子串在主串中的起始位置}}return -1; // 子串未找到
}朴素匹配算法是一种简单直观的字符串匹配算法但它也存在一些缺点
效率较低朴素匹配算法的时间复杂度为O(n*m)其中n为主串的长度m为子串的长度。在最坏的情况下需要进行大量的字符比较和回溯操作导致算法效率较低。 回溯次数较多当主串中的某个字符与子串的第一个字符匹配但后续字符不匹配时朴素匹配算法需要回溯到主串中的下一个位置继续进行匹配。这可能导致大量的回溯操作影响算法的性能。 没有利用已有信息朴素匹配算法没有利用已经匹配过的字符信息每次都从头开始比较。这使得算法的效率较低尤其是在处理大规模文本时。
所以需要改进算法。
四、升级版的匹配算法KMP模式匹配算法
1.背景如果主串 S“aabaabaaf” 要匹配的子串为 T“aabaaf” 。
朴素匹配算法时主串从第一位开始逐次与子串比较比较一圈不匹配后又从第二位开始逐次与子串比较如此往复。那么主串需要不断的回溯之前比较时得到的信息没有充分利用。
2.KMP算法解决的问题字符串匹配中将时间复杂度从Om*n缩短到Omn
3.浅显的KMP匹配过程
1第一次匹配时a-a、a-a、b-b、a-a、a-a、b-f,这时不一致了。 2我不想回溯重新匹配所以第二次匹配让子串跳到从b之后开始匹配这样的话刚好一个循环就能完成匹配。所以KMP算法重要的思想就是省略了普通算法中逐次比较的第2、3、4、5、、、步只进行了第1步和可以成功匹配的最后一步。
4.关键在于如何得知让子串跳到哪个位置去跟主串比较呢这里是b——求最长相等前后缀
①一个串的前缀和后缀是什么
一个字符串的前缀是指从开头到某个位置的子串后缀是指从结尾到某个位置的子串。换句话说给定一个字符串S它的前缀是S的任意一个以开头的子串而后缀是S的任意一个以结尾的子串。
例如对于字符串ABCD它的前缀包括“” (空串)“A”“AB”“ABC”而后缀包括“BCD”“CD”“D”“” (空串)。
②子串为 T“aabaaf” 的前缀和后缀是什么
前缀a、aa、aab、aaba、aabaa 后缀f、bf、abf、aabf、baabf、abaaf 记忆技巧前缀有头无尾 后缀有尾无头
③什么叫最长相等前后缀
子串都有自己的前缀和后缀对每个前缀进行分析看看他们的前后缀有没有相同的有几项就记录为几。
根据子串的前缀来分析子串前缀的前后缀 比如aaba前缀a和后缀a相同长度为1前缀aa和后缀ba不同前缀aab和后缀aba不同。 比如aabaa前缀aa和后缀aa相同长度为2是最长的。
这个东西叫做前缀表。
④根据前缀表求匹配
第一次匹配后b≠f那么要找f前面的子串的最长相等前后缀即为2。 数字2意味着什么呢f之前的前缀是aabaa意味着后缀aa和前缀aa刚好形成了一个相同且对称的形式。而我们要让第二次匹配时子串跳到b的位置去因为b在子串的这个数组里刚好下标就是2。 所以第二次匹配时子串就从主串的b位置开始逐一比较。省略了前面的一些繁琐的步骤简化了时间复杂度。
⑤next数组是什么
就是求出最长的相等的前后缀把长度记录到next数组中。 next数组当主串与子串的某一位字符不匹配时子串要回退的位置。
⑥KMP算法的思想不难难的是如何计算最长相同前后缀和next数组。
五、 KMP算法再举一个例子
主串ababbaabbaababaaacb
子串ababaa
1手算求next数组求子串每个字母和前面一坨的最长公共前后缀长度
①a前面没有就是0 ②ab前缀a后缀a长度为1 ③aba前缀a后缀a前缀ab后缀ba长度为1 ④abab前缀ab后缀ab,长度为2 ⑤ababa前缀aba后缀aba长度3 ⑥ababaa前缀a后缀a长度1 所以前缀表 a b a b a a 0 1 1 2 3 1 所以next数组 a b a b a a -1 0 0 1 2 0
(2)KMP过程 这样不断让子串往后面对齐移动其中省略掉的就是不用让子串每次重新回到主串头位置了根据已有的信息巧妙地省略掉了公共的、无意义的比较过程。
六、KMP算法的代码实现
1.求next数组
void calculateNext(char *pattern, int *next) {int len strlen(pattern);int i 0, j -1;next[0] -1;while (i len) {if (j -1 || pattern[i] pattern[j]) {i;j;next[i] j;} else {j next[j];}}
}函数 calculateNext 用于计算模式串的 Next 数组。
首先获取模式串的长度 len并初始化两个指针 i 和 j其中** i 表示当前遍历到的位置j 表示前缀的末尾位置**。
然后将** Next 数组的第一个元素 next[0] 设置为 -1表示不存在前缀**。
接下来使用一个循环从索引 1 开始遍历子串的字符
如果 j 等于 -1 或者当前字符 pattern[i] 等于前缀的末尾字符 pattern[j]则说明可以扩展当前位置的前缀长度即 i 和 j然后将 j 的值赋给 next[i]。 如果当前字符不匹配则需要回溯到更短的相等前后缀。将 j 更新为 next[j]即回溯到前缀的前缀。 最后循环结束后Next 数组中存储了每个位置的最长相等前后缀的长度。
这个函数的目的是为了通过利用已匹配的部分避免无谓的字符比较从而提高字符串匹配的效率。
2.KMP算法
思路先获取next数组然后
int kmpSearch(char *text, char *pattern) {int textLen strlen(text);int patternLen strlen(pattern);int i 0, j 0;int next[patternLen];calculateNext(pattern, next);while (i textLen j patternLen) {//条件为 i 小于文本串的长度且 j 小于模式串的长度if (j -1 || text[i] pattern[j]) {//如果 j 等于 -1 或者当前文本串字符 text[i] 等于模式串字符 pattern[j]i;//说明当前字符匹配成功,继续比较下一个字符即 i 和 jj;} else {j next[j];//如果当前字符不匹配则需要根据 Next 数组来进行回溯//将模式串向右移动到最大匹配的位置}}if (j patternLen) { //j 等于模式串的长度return i - j; // 已完全匹配成功,返回匹配的起始位置} else {return -1; // 没有找到匹配的子串}
}函数 kmpSearch 是使用 KMP 算法在文本串中查找匹配的子串。
首先获取文本串和模式串的长度并初始化两个指针 i 和 j分别指向文本串和模式串的起始位置。 然后创建一个长度为模式串长度的 Next 数组并调用 calculateNext 函数来计算模式串的 Next 数组。
接下来使用一个循环条件为 i 小于文本串的长度且 j 小于模式串的长度 如果 j 等于 -1 或者当前文本串字符 text[i] 等于模式串字符 pattern[j]则说明当前字符匹配成功继续比较下一个字符即 i 和 j。 如果当前字符不匹配则需要根据 Next 数组来进行回溯。将 j 更新为 next[j]即将模式串向右移动到最大匹配的位置。
循环结束后有两种情况 如果 j 等于模式串的长度表示模式串已完全匹配成功返回匹配的起始位置 i - j。 如果 j 不等于模式串的长度表示没有找到匹配的子串返回 -1。
