基本信息
文件名称:计算机算法设计与分析(第6版)-课件 ch0903序列比较算法.pptx
文件大小:3.48 MB
总页数:26 页
更新时间:2025-10-11
总字数:约2.71千字
文档摘要
序列比较算法
01从串到子序列
串与子序列的定义在序列算法中,串是指连续的字符序列,而子序列则允许字符之间有间隔。例如,abc是abracadabra的子序列,但不是子串。子序列的生成方式子序列可以通过从原始串中删除若干字符(可以是零个)得到,而不需要保持字符的连续性。这为序列比较提供了灵活性。真子序列的概念当一个子序列不等于原串时,我们称其为真子序列。例如,ab是abc的真子序列,因为它严格包含于原串。串与子序列的本质差异
02编辑距离透视
Levenshtein距离三元操作三种基本操作编辑距离算法基于三种基本操作:替换、插入和删除。这些操作的代价通常用Levenshtein度量来衡量,满足