串的定义

• 串是由零个或多个字符组成的有限序列，又叫字符串，一般记为s=“a1a2......an”(n>=0)，其中s是串的名称，串中的字符数目n称为串的长度，零个字符的串称为空串

串的比较

• 串的比较是通过组成串的字符之间的编码来进行的，字符的编码指的是字符在对应字符集中的符号
• 不相等时：s=“a1a2...an”，t=“b1b2...bm”，s<t
  1. n<m,ai=bi
  2. k<=min(m,n),ai=bi,ak<bk

串的抽象数据类型

串的存储结构

• 串值的存储空间可在程序执行过程中动态分配而得，比如计算机中存在一个自由存储区，叫做“堆”

串的链式存储结构

• 一个结点对应一个字符，存在很大的空间浪费，一个结点可以存放一个字符，也可以考虑存放多个字符
• 链式存储结构整体不如顺序存储结构灵活，性能也不如顺序存储结构

朴素的模式匹配算法

• 字串的定位操作通常称做串的模式匹配
• 对主串的每一个字符作为字串开头，与要匹配的字符串进行匹配，对主串做大循环，每个字符开头做T长度的小循环，直到匹配成功或全部遍历

串的定义

• 串是由零个或多个字符组成的有限序列，又叫字符串，一般记为s=“a1a2......an”(n>=0)，其中s是串的名称，串中的字符数目n称为串的长度，零个字符的串称为空串

串的比较

• 串的比较是通过组成串的字符之间的编码来进行的，字符的编码指的是字符在对应字符集中的符号
• 不相等时：s=“a1a2...an”，t=“b1b2...bm”，s<t
  1. n<m,ai=bi
  2. k<=min(m,n),ai=bi,ak<bk

串的抽象数据类型

串的存储结构

• 串值的存储空间可在程序执行过程中动态分配而得，比如计算机中存在一个自由存储区，叫做“堆”

串的链式存储结构

• 一个结点对应一个字符，存在很大的空间浪费，一个结点可以存放一个字符，也可以考虑存放多个字符
• 链式存储结构整体不如顺序存储结构灵活，性能也不如顺序存储结构

朴素的模式匹配算法

• 字串的定位操作通常称做串的模式匹配
• 对主串的每一个字符作为字串开头，与要匹配的字符串进行匹配，对主串做大循环，每个字符开头做T长度的小循环，直到匹配成功或全部遍历
  
  
• 最好的时间复杂度：O(1)
• 最坏的时间复杂度：O((n-m+1)*m)

KMP模式匹配算法

原理

• 最好的时间复杂度：O(1)
• 最坏的时间复杂度：O((n-m+1)*m)

KMP模式匹配算法

原理

• 避免让没必要的回溯发生
• j值的多少取决于当前字符之前的串的前后缀的相似度
• 我们把T串各个位置的j值变化定义为一个next数组：
  —————| 0,当j=1
  next[j]=——| Max{k|1<k<j,且'p1 ... k-1'='p j-k+1 ... pj-1'}当此集合不空
  —————| 1，其他情况
• 经验可得，如果前后缀n个字符相等，k值就是n+1
• 去掉了i值回溯的部分，时间复杂度为O(n),整个算法的时间算法度为O(n+m)