字符串是一串文字及符号的简称，是一种特殊线性表。
字符串的基本数据元素是字符。
（一）串的定义
串：是仅由字符构成的有限序列，是取值范围受限的线性表。
串长：串的长度，指字符串中的字符个数.
空串：长度为0的串，空串不包含任何字符。
空格串：由一个或多个空格组成的串。空白符也是字符，计算串长度时要将其计算在内。
子串：由串中任意长度的连续字符构成的序列称为子串。
主串：含有子串的串。
子串在主串中的位置：指子串首次出现时，该子串的第一个字符在主串的位置。
空串：是任意串的子串。
串相等：指两个串长度相等且对应位置上的字符也相同。
串比较：两个串比较大小时，以字符ASCII码值作为依据。从两个串的第一个字符开始比较，字符ASCII码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。
（二）串的基本操作
①赋值操作StrAssign（s，t）：将串t的值赋给串s。
②连接操作Concat（s，t）：将串t接续在串s的尾部，形成一个新串。
③求串长StrLength（s）：返回串s的长度。
④串比较StrCompaie（s.t）：比较两个串大小。返回值-1、0和1分别表示s<t、s=t和s>t三种情况。
⑤求子串SubString（s，start，len）:返回串s中从start开始、长度为len的字符序列。
（三）串的存储结构
存储结构 | 说明 | 备注 | |
1 | 顺序存储 | 用一组地址连续的存储单元来存储串值的字符序列。 串中元素为字符，可通过程序语言提供的字符数组定义串的存储空间（即存储空间容量固定），也可根据串长的需要动态申请字符串空间（即存储空间容量可扩充或缩减）。 | |
2 | 链式存储 | 字符串也可以采用链表作为存储结构，当用链表存储串中字符时，每个结点中可存储一个字符或多个字符，需要考虑存储密度问题。 | 结点大小的选择和顺序存储方法中数组空间大小的选择一样重要，直接影响串处理效率。 |
通常情况下，字符串存储在一维字符数组中，每个字符串末尾都有一个串结束符，在C/C++程序中以特殊字符“\0”作为结束标记。
（四）字符串运算
大多数程序语言在其开发资源包中，都提供了字符串赋值（拷贝）、连接、比较、求串长、求子串等基本运算。
（五）串的模式匹配
子串（模式串）在主串中的定位操作常称为串的模式匹配。
（1）基本模式匹配算法
该算法也称为布鲁特-福斯（Brute-Force）算法，是一种带回溯的朴素的模式匹配算法。
基本思想：将S（主串）与T（子串）进行匹配过程中，成功返回对应的start（某次匹配时主串的开始位置），否则 start 加1，重新开始匹配，直至匹配成功或者start到了S末尾。
该算法在最坏情况下的时间复杂度为O(n×m)。（主串长度为n，模式串长度为m）
（2）改进的模式匹配算法
KMP算法：属于改进的模式匹配算法。核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
改进之处：在匹配失败时，“会从中吸取信息”，得到主串中 start 位置后面某些位肯定无法匹配上的位置，跳过这些位置，start 加到下次可能会匹配的上的位置。具体实现是通过一个next数组实现，函数本身包含了模式串的局部匹配信息。
此算法以空间复杂度换取了时间复杂度。可在O(n+m)时间内完成。
