烟台高端网站制作公司,丹东振兴区,招聘网站内容建设,如何做好网站建设前言
本文基础知识部分来自于b站#xff1a;分享笔记的好人儿的思维导图与王道考研课程#xff0c;感谢大佬的开源精神#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析#xff0c;本人技术…前言
本文基础知识部分来自于b站分享笔记的好人儿的思维导图与王道考研课程感谢大佬的开源精神习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析本人技术有限最终数据清洗结果不够理想相关CSDN文章便没有发出。
考研真题待更新 欢迎订阅专栏408直通车 请注意本文中的部分内容来自网络搜集和个人实践如有任何错误请随时向我们提出批评和指正。本文仅供学习和交流使用不涉及任何商业目的。如果因本文内容引发版权或侵权问题请通过私信告知我们我们将立即予以删除。 文章目录 前言第四章 串串的定义与实现概念小结 串的存储结构和线性表几乎一样仅将存储数据的类型改为字符顺序存储结构链式存储结构小结 块链存储结构 串的模式匹配简单模式匹配算法KMP算法手算 进一步优化 代码王道代码见教材补充代码 考研真题408 - 2023 第四章 串
串的定义与实现
概念 串的概念 零个或多个任意字符组成的有限序列内容受限的线性表 子串的概念 一个串中任意个连续字符组成的子序列含空串 小结 串的存储结构和线性表几乎一样仅将存储数据的类型改为字符
顺序存储结构 char 8bit 0~255
链式存储结构 一个结点若只存一个字符存储密度过低引出块链存储结构
小结 块链存储结构
每个结点既可以存放一个字符也可以存放多个字符。每个结点称为块
串的模式匹配
简单模式匹配算法 概念 子串的定位操作通常称为串的模式匹配它求的是子串模式串在主串中的位置 算法思想 将主串中与模式串长度相同的子串逐个与模式串匹配暴力法 缺点 主串指针回溯导致时间开销时间复杂度为O(nm)nm分别为主串和模式串的长度
KMP算法 基本概念 前缀 除最后一个字符外字符串的所有头部子串 后缀 除第一个字符外字符串的所有尾部子串 算法思想 主串指针不必回溯模式串指针根据next数组部分回溯如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀可以将模式串向后滑动到与这些相等字符对齐的位置 next数组 表明当模式中第j个字符与主串中相应字符匹配失败时在模式中需重新和主串中该字符进行比较的字符位置 即衡量模式串向后滑动的量 计算 以“abab”为例 序号j 1时属于j 1情况next[j] 0 序号j 2时‘a’的前后缀都为空集属于其他情况next[j] 1 序号j 3时‘ab’的前缀为{a}后缀为{b}交集为空属于其他情况next[j] 1 序号j 4时‘aba’的前缀为{a,ab}后缀为{a,ba}交集为{a}k - 1 1长度next[j] k 2长度1 时间复杂度O(m n)
手算 1 2 3 4 5 6 进一步优化
构造nextval数组 若模式串指向的位置的字符等于本身可以直接赋值 举例 5号的a中next数组指向3号位置3号位置也是a故直接把3号的next数组值复制过去 6号的a中next数组指向4号位置两者字符不同不能优化
代码 王道代码见教材
补充代码 cin n p1 m s1;// char数组s是长文本p是模式串且从数组下标1开始存储
for(int i2,j0;in;i){ //求next数组while(jp[i]!p[j1]) jne[j];if(p[i]p[j1]) j;ne[i]j;
}
for(int i1,j0;im;i){ //匹配while(js[i]!p[j1]) jne[j];if(s[i]p[j1]) j;if(jn){jne[j];//匹配成功}
}考研真题
408 - 2023
考研真题待更新
