一、串的基本概念
字符串是零字符或更大的有限序列。 设定str='a0a1…an-1'(n0 )。
字符串中包含的字符数n称为字符串长度，如果n=0，则称为空字符串。
由字符串中的任意连续字符组成的子串称为字符串的子串。
包含子字符串的字符串相应地被称为主字符串。
如果两个字符串长度相等，且所有对应的字符都相等，则两个字符串称为相等。
假设s是长度为n的字符串，其中的字符各不相同，那么s中所有子串的个数是多少？
二、字符串的抽象数据类型
三、串的记忆结构
字符串顺序存储结构-顺序
与顺序表一样，序列由data数组和整数变量size表示，size表示data数组中实际的字符数。
为了简单起见，data数组采用固定容量MaxSize (可以模仿顺序表改为动态容量方式)。
顺控系统sq字符串
序列上基本运算算法的设计与序列表相似，仅以求子串为例进行说明。
求子串：对一个序列求出编号I的开始长度为j的子串。
实现：首先创建空字符串s，如果参数正确，则s子串的字符串为data[i.i j-1]的合计j个字符，如果I和i j-1不在有效序列号0~size-1的范围内，则参数出错，导致错误
设计按词典顺序比较两个字母串s和t的大小的算法strcmp(s，t )，假设两列都按顺序存储。
链的存储结构-链
用开头节点的单链表来表示链
例如，s='ABCDEFGHIJKLMN '，总共14个字符。
链接的节点类型LinkNode (节点大小为1 ) ) ) )。
一个链接由一个头节点head唯一识别，链接系统LinkString
链上的基本运算算法类似于单链表，但以链插入算法为例进行说明。
串插入：链串在编号I的位置插入串t
2c61bc631151?from=pc">实现：先创建一个空串s，当参数正确时，采用尾插法建立结果串s：
（1）将当前链串的前i个结点复制到s中。
（2）将t中所有结点复制到s中。
（3）再将当前串的余下结点复制到s中。
串的模式匹配
设有两个串s和t，串t定位操作就是在串s中查找与子串t相等的子串。
通常把串s称为目标串，把串t称为模式串，因此定位也称作模式匹配。
模式匹配成功是指在目标串s中找到一个模式串t。
不成功则指目标串s中不存在模式串t。
BF算法
思路：目标串s="s0s1…sn-1"，模式串t="t0t1…tm-1"
第1趟：从s0/t0开始比较，若相等，则继续逐个比较后续字符。如果对应的字符全部相同且t的字符比较完，说明t是s的子串，返回t在s中的起始位置，表示匹配成功；如果对应的字符不相同，说明第一趟匹配失败。
第2趟：从s1/t0开始比较，若相等，则继续逐个比较后续字符。如果对应的字符全部相同且t的字符比较完，说明t是s的子串，返回t在s中的起始位置，表示匹配成功；如果对应的字符不相同，说明第一趟匹配失败。
依次类推。只要有一趟匹配成功，则说明t是s的子串，返回t在s中的起始位置。如果i超界都没有匹配成功，说明t不是s的子串，返回-1。
BF算法性能
该算法在最好情况下的时间复杂度为O(m)，即主串的前m个字符正好等于模式串的m个字符。
最坏情况下的时间复杂度为O(n×m)。
平均情况下的时间复杂度为O(n×m)。
KMP算法
主要是消除了目标串指针的回溯，从而使算法效率有了某种程度的提高。
KMP算法性能
设目标串s的长度为n，模式串t长度为m。
在KMP算法中求next数组的时间复杂度为O(m)。
在后面的匹配中因主串s的下标i不减即不回溯，比较次数可记为n。
KMP算法总的时间复杂度为O(n+m)。
例子：设目标串s="ababcabcacbab"，模式串t="abcac"。给出KMP进行模式匹配的过程。
KMP算法的性能提高了吗？
KMP算法跳过了中间一些趟，正确吗？
例子：设s="aaabaaaab"，t="aaaab"。计算模式串t的nextval函数值。并画出利用改进KMP算法进行模式匹配时每一趟的匹配过程。
例子：设目标串为s="abcaabbabcabaacbacba"，模式串t="abcabaa"。计算模式串t的nextval函数值。并画出利用KMP算法进行模式匹配时每一趟的匹配过程。