【数据结构】考研真题攻克与重点知识点剖析 - 第 4 篇:串

2024-04-07 06:28

本文主要是介绍【数据结构】考研真题攻克与重点知识点剖析 - 第 4 篇:串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

  • 本文基础知识部分来自于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 >> p+1 >> m >> s+1;// char数组s是长文本,p是模式串,且从数组下标1开始存储
    for(int i=2,j=0;i<=n;i++){  //求next数组while(j&&p[i]!=p[j+1]) j=ne[j];if(p[i]==p[j+1]) j++;ne[i]=j;
    }
    for(int i=1,j=0;i<=m;i++){  //匹配while(j&&s[i]!=p[j+1]) j=ne[j];if(s[i]==p[j+1]) j++;if(j==n){j=ne[j];//匹配成功}
    }
    

考研真题

408 - 2023

(考研真题待更新)

这篇关于【数据结构】考研真题攻克与重点知识点剖析 - 第 4 篇:串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881858

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

前端知识点之Javascript选择输入框confirm用法

《前端知识点之Javascript选择输入框confirm用法》:本文主要介绍JavaScript中的confirm方法的基本用法、功能特点、注意事项及常见用途,文中通过代码介绍的非常详细,对大家... 目录1. 基本用法2. 功能特点①阻塞行为:confirm 对话框会阻塞脚本的执行,直到用户作出选择。②

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

基本知识点

1、c++的输入加上ios::sync_with_stdio(false);  等价于 c的输入,读取速度会加快(但是在字符串的题里面和容易出现问题) 2、lower_bound()和upper_bound() iterator lower_bound( const key_type &key ): 返回一个迭代器,指向键值>= key的第一个元素。 iterator upper_bou

三国地理揭秘:为何北伐之路如此艰难,为何诸葛亮无法攻克陇右小城?

俗话说:天时不如地利,不是随便说说,诸葛亮六出祁山,连关中陇右的几座小城都攻不下来,行军山高路险,无法携带和建造攻城器械,是最难的,所以在汉中,无论从哪一方进攻,防守方都是一夫当关,万夫莫开;再加上千里运粮,根本不需要打,司马懿只需要坚守城池拼消耗就能不战而屈人之兵。 另一边,洛阳的虎牢关,一旦突破,洛阳就无险可守,这样的进军路线,才是顺势而为的用兵之道。 读历史的时候我们常常看到某一方势

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚: