在数据结构的学习中,串是一种重要的数据类型,它是由一个或多个字符组成的有限序列。本章主要讨论了串的相关概念、操作以及算法。以下是基于题目内容的详细知识点解析: 1. **串的定义**:串是字符的有限序列,可以为空,但空串不等同于由空格构成的串。因此,选项B是错误的。 2. **串的操作**:模式匹配是串的基本运算之一,用于在一个串中查找另一个串(模式串)的出现位置。题目中的表达式涉及到了`concat`(连接)、`replace`(替换)、`substr`(子串提取)和`index`(查找子串首次出现的位置)等操作。 3. **子串与匹配**:如果一个串q是另一个串p的子串,那么在p中首次出现q的位置的算法称为匹配。例如,题目中的选项C对应的就是这种匹配算法。 4. **Next数组**:Next数组是KMP算法中的一个重要概念,用于记录模式串中每个字符前缀和后缀的最大公共长度。例如,对于串S=‘aaab’,Next数组是1123,表示在每个位置i,模式串的前i个字符与从i+1开始的最长公共前缀的长度。 5. **next数组和nextval数组**:next数组记录的是模式串中连续字符的最大公共前缀长度,而nextval数组则考虑了回溯的情况,例如串‘ababaabab’的next数组为012301232,nextval数组为0112322345。 6. **子串计数**:一个串的子串数目可以按照特定的公式计算,例如,串S=‘software’的子串数目是37,包括空串和自身。 7. **非平凡子串**:一个长度为n的字符串S中的互异非平凡子串(非空且不同于S本身)的个数为(n^2/2) + (n/2) - 1。这个数量不包括S本身和空串。 8. **串的长度**:串的长度是指串中字符的个数,包括空格。所以,选项B是错误的,串的长度不是不同字符的个数,也不是非空格字符的个数。 9. **KMP算法**:KMP算法在模式匹配时避免了不必要的回溯,即主串的指针不会变小,这是它的特点之一。 10. **串的特殊性质**:串作为一种特殊的数据结构,它的数据元素只能是字符,并且串的操作通常包括插入、删除、连接、查找、替换等。 填空题: 1. **空格串**:空格串是指由零个字符组成的串,其长度等于0。 2. **数据元素**:组成串的数据元素只能是字符。 3. **字**:由于题目未提供完整信息,这里假设是询问“字”的定义,字通常指单个的字符。 以上就是关于数据结构中第四章串的相关知识点,涵盖了串的定义、操作、模式匹配、Next数组等相关概念及其应用。
![application/x-dosexec](https://img-home.csdnimg.cn/images/20210720083343.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![thumb](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/default.jpg!1)
- 粉丝: 2
- 资源: 6
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)