为什么求解“最长公共子序列”(LCS)需要递归函数?——从“公共子串”的角度来分析问题(附程序和VB源文件)

我们知道:公共子序列是由一个个公共子串顺序连接而成的。为了求“最长公共子序列”,可以把字符串中的字分成2类:一类是要留下的(组成公共子串),另一类是要出列的。我们可以编程,把字符串(我取下面一行,txt2)从头到尾逐字鉴定该留还是该出列。 别看字符串五花八门、长长短短,鉴定起来却只有4种情况。而且并不是每一种都需要调用递归函数的。 我在【图一】中的每个公共子串的右面画一根蓝色竖线,表示原公共子串结束,新公共子串开始。 (下面所说的“情况一、情况二”,都可以用我们熟悉的、简单的编程语句来完成的。) 情况一:看第1个字“他”,上下2个字一样,“他”就留下,这情况我称为①。后面...
默认分类 | 2022-12-09 16:57 | 阅读 3409 次 | 评论 0 条
浏览91093次
文章分类