全部类别

字符串算法4

在字符串和序列上完成模式匹配、编辑比较与差异计算。

字符串匹配

在文本中查找模式的出现位置。单模式与多模式的复用方式不同,还要区分字节、字符或其他符号序列的匹配语义。

适用条件与算法对照
Myers DiffMyers difference algorithm

在编辑图上逐层扩展可达路径,寻找较短的编辑脚本。

经典算法 O(ND)O(ND),N 为输入总长,D 为编辑距离
Patience DiffPatience difference algorithm

先以双方唯一的公共行建立有序锚点,再比较锚点之间的片段。

唯一行匹配、最长递增子序列与回退算法共同决定成本
4 个概念