[数据结构与算法]邓公数据结构与算法第十三章 串 ADT

ADT

定义和特点

特点：串长远远大于字符种类

术语

ADT接口实现

模式匹配

问题与需求

主要解决4个问题。

算法测试方法

成功与失败的情况分开来测试。

蛮力匹配

构思

• 自左向右，以字符为单位，依次移动模式串直到在某个位置发现匹配
  

蛮力匹配：版本1

• return i-j

i-j 大于n-m 即可判定失败。因为失败时 （字符串T）i=n，（模板串P）j<m。
i-j<=n-m 即可判定成功
i-j的意义是字符串中与模板串开始比较的位置。

蛮力匹配：版本2

蛮力匹配：性能分析

1. 最好最坏情况复杂度分析

1. 最坏情况例子

字母表={0,1}
成功次数m-1次，失败次数1

2. 特点
   

3. 蛮力算法为何低效

• 有重复匹配的前缀：即一个字符串T中的一个位置需要比对多次。
• 不变性：模板P总是右移一位去比对。不会根据情况改变

KMP算法

查询表

理解next【】表

理解N ( p , j ）={ 0 <= t<j | P [ 0, t ) == P[ j-t , j ) };

1. 具有特点：
   快速右移
   避免回溯
   next【0】=-1

构造next【】表

1. 当p【j】== p【 next [ j ] 】

计算next【j+1】

2. 当p【j】！= p【 next [ j ] 】时

next【】表代码实现

KMP复杂度准确分析 ——线性时间O（n）

设一个k=2i-j （分析方法忽略吧）

KMP算法改进版

改进的原因：在当前模式串P的元素重复，使得连续与文本串T的元素进行对比失败，产生冗余，故可跳过相同元素与T的重复比对，提高KMP算法性能