第四章串
4.1 定义和实现
4.1.1 定义
串，即字符串（String）是由零个或多个字符组成的有限序列。
T=‘iPhone 11 Pro Max?’
子串：串中任意个连续的字符组成的子序列。 Eg：’iPhone’，’Pro M’是串 T 的子串
主串：包含子串的串。 Eg：T 是子串’iPhone’的主串
字符在主串中的位置：字符在串中的序号。 Eg：’1’在 T 中的位置是 8 (第一次出现)
子串在主串中的位置：子串的第一个字符在主串中的位置。 Eg：’11 Pro’在 T 中的位置为
串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
串的基本操作，如增删改查等通常以子串为操作对象
串的基本操作
StrAssign (&T, chars)：赋值操作。把串 T 赋值为 chars。
StrCopy (&T, S)：复制操作。由串 S 复制得到串 T。
StrEmpty (S)：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。
StrLength (S)：求串长。返回串 S 的元素个数。 ClearString (&S)：清空操作。将 S 清为空串。
DestroyString (&S)：销毁串。将串 S 销毁（回收存储空间）。
Concat (&T, S 1, S 2)：串联接。用 T 返回由 S 1 和 S 2 联接而成的新串
SubString (&Sub, S, pos, len)：求子串。用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
Index (S, T)：定位操作。若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为 0。
StrCompare (S, T)：比较操作。若 S>T，则返回值 > 0；若 S=T，则返回值 = 0；若 S
4.1.2 串的存储结构
顺序存储
4.1.3 基本操作
- 求子串
- 比较
- 定位
4.2 串的模式匹配
4.2.1 简单的模式匹配算法
串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置
N 为主串长度 m 为模式串长度
朴素模式匹配算法 ：将主串中所有长度为 m 的子串依次与模式串对比，直到找到一个完全匹配的或所有的子串都不匹配为止
当前子串匹配失败：主串指针 i 指向下一个子串的第一个位置，模式串指针 j 回到模式串的第一个位置
当前子串匹配成功：返回当前子串第一个字符的位置
直到匹配成功 / 匹配失败最多需要 (n-m+1)*m 次比较
最坏时间复杂度：O (nm)
4.2.2 KMP 算法
最坏时间复杂度：O (m+n)
