Carson带你学数据结构：这是一份全面 & 详细的”串“讲解指南

谁借莪１个温暖的怀抱￠ 2023-06-22 10:26 34阅读 0赞

![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

# 前言 #

本文主要讲解 数据结构中的串，内容包括其特点、结构等，希望你们会喜欢。

--------------------

# 目录 #

![示意图][format_png]

--------------------

# 1. 简介 #

![示意图][format_png 1]

--------------------

# 2. 存储结构介绍 #

包括：顺序存储结构 & 链式存储结构

![示意图][format_png 2]

--------------------

# 3. 串的比较 #

![示意图][format_png 3]

--------------------

# 4. 子串的定位 #

*  子串定位 的主要任务是：确定主串是否存在子串 & 子串在主串中的位置

> 子串的定位操作 也称 **串的模式匹配**

*  下面主要讲解串模式匹配的重要方法：`KMP`模式匹配算法

### 4.1 KMP模式匹配算法 简介 ###

![示意图][format_png 4]

### 4.2 具体算法 ###

*  概念：字符串的前缀 & 后缀

![示意图][format_png 5]

*  具体使用  
    步骤1：计算出子串（T串）各个位置的 `j` 值的变化  
    步骤2：根据步骤1计算出的`next`数组，将子串与主串进行模式匹配

![示意图][format_png 6]

下面将重点讲解步骤1：**计算出子串（T串）各个位置的 `j` 值的变化**

*  定义1数组：`next [ j ]` = 子串（T串）各个位置的 `j` 值的变化

> `j` 值仅取决于：`T`串 当前字符 前后缀字符的相似度

*  `next [ j ]`值的函数定义如下  
    ![示意图][format_png 7]
 *  举例说明

![示意图][format_png 8]

### 4.3 算法改进 ###

![示意图][format_png 9]

--------------------

# 5. 总结 #

*  本文主要讲解了 数据结构中 串的知识，含 其特点、结构等
 *  下面我将继续对 **数据结构**进行讲解，有兴趣可以继续关注[Carson\_Ho的安卓开发笔记][Carson_Ho]

--------------------

# 请帮顶 / 评论点赞！因为你的鼓励是我写作的最大动力！ #

[e42c52b9af8d79486a0f3cd0e50df7b7.png]: https://img-blog.csdnimg.cn/img_convert/e42c52b9af8d79486a0f3cd0e50df7b7.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0wODg1OTBlNjdiZjBlMGU3LnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1jNTFhNDExNTdhMzZlZTJhLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iNTdiZjgwZGNkYWIzZTg0LnBuZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0zNTYyODNiOTgyNWFlODMzLnBuZw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS02YmQ0MWU4MDFjNzM5MTM2LnBuZw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0wYjdmNmQ4MGFmMGM0M2UxLnBuZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS04ODFiZjJhNzU3NGQ2NzYwLnBuZw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS01MzRhMDM0ZThmMDcyOGM2LnBuZw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS00YTg0MDVmMWZmOGM4ZWE4LnBuZw?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0xYzFlMDZmNmQ1NGY3YTYyLnBuZw?x-oss-process=image/format,png
[Carson_Ho]: https://blog.csdn.net/carson_ho