串的知识梳理思维导图

串是一种线性结构，是由零个或多个字符组成的有限序列，也可以称之为字符串。在计算机中，我们通常使用ASCII或Unicode编码表示一个字符，从而可以将字符序列转化为一个串

空串是指长度为零的串，也可以称为空字符串。它是一个特殊的串，不包含任何字符。例如，""就是一个空串

子串是指在一个串中任意选取一段连续的字符组成的串，也可以称为子字符串。例如，在串"hello world"中，"hello"和"world"都是它的子串

主串是指包含子串的串，也可以称为源字符串或母串。例如，在串"hello world"中，"hello world"是主串。

空格串是指由空格字符组成的串，也可以称为空白串。例如，" "和" "都是空格串。

串的长度是指一个串中包含的字符数，也可以称为串长。例如，串"hello world"的长度是11。

BP算法是一种朴素的串匹配算法，也称为暴力匹配算法。它的基本思想是在文本串中从左到右依次比较子串和模式串中的字符，当子串和模式串完全匹配时，返回在文本串中的位置；否则，继续比较下一个位置，直到找到匹配或遍历完整个文本串。

KMP算法是一种高效的串匹配算法，它利用模式串的自重复性，在匹配过程中避免重复比较已经匹配的字符。KMP算法的核心部分是获取模式串的next数组，然后利用next数组进行匹配。

在串的定长顺序存储表示中，串被存储在一个定长数组中，该数组的长度为串的最大长度，通常用字符型数组来存储，每个元素存储一个字符。由于数组的长度是固定的，因此称为定长数组。

在串的动态分配存储表示中，串被存储在一个动态分配的存储区中，该存储区的大小根据串的实际长度动态调整，不会浪费空间。通常使用指针来表示动态分配存储的串。

在串的链式存储模式中，串被存储在一个链表中，每个结点表示一个字符。通常使用链表中的结点来表示字符，结点中包含一个指向下一个结点的指针和一个表示字符的数据域。