04串

串的定义和实现

顺序存储串的弊端
串的实际长度只能小于或等于 MAXLEN,超过预定义长度的串值会被舍去,称为截断

在一些串的操作(如插入,联接等)中,若串值序列的长度超过上界 MAXLEN,约定用”截
断”法处理,要克服这种弊端,只能不限定串长的最大长度,即采用动态分配的方式.

动态分配的方式
堆分配存储
块链存储

串的模式匹配

和 分别为主串和模式串的长度.
简单匹配(暴力匹配)算法的最坏时间复杂度为 {c1:}
但在实际使用中,时间复杂度为{c1:}

Q: 为什么KMP 算法可以在的时间数量级上完成串的模式匹配操作
A: 整个匹配过程中,主串始终没有回溯

KMP串匹配算法使用next数组的计算方法
使用前缀后缀比较方法

Q: KMP算法进一步优化
用nextVal[n]取代next[n]
A: 用了递归判断
第i个字符不匹配

• 比较第next[i]个字符与第i个字符是否相同
  • 相同
    • next[i]=next[next[i]]
    • 再次比较第next[i]个字符与第i个字符是否相同
    • 进入递归 直到第next[i]个字符与第i个字符不相同
  • 不相同
    • next[i]不变