LCS“最长公共子序列”的另一解题思路(绕开 6 X 7 宫格)----附件有自编的程序

默认分类 | 2020-09-03 12:40:50 | 阅读 924 次 | 评论(0)

演示.png (上传于2020-09-11 17:04:47)
演示.png

0902-1.png (上传于2020-09-08 11:13:19)
0902-1.png

为什么这个程序既可以验证一些网上LCS论文中举出的“短字符例题”(图一),也可以对代码稍作更改后,在1秒内求出近千字的“(无提醒打错的)中文打字测验”文本的“正确字数”(图二)。相信你在看了我下面的的描述后,应该可以有所明白。

    两个字串的“最长公共子序列”可以从这样的角度描述:有上下两个字串,把下字串从左到右每一个字在上面“找到相同的字”并“连线”。
    有2个要求:1.连线不许交叉。2.连线数“最多”。于是,在两个字串中“剔除”了“无法连线”的字之后,剩下的字串就是“最长公共子序列”了。
    ★连线有3种情况,2种非常简单,1种非常复杂。
    1.正是对面的“下一个”,直接连线就是了。(图三中的“A”)
    2.遍寻不在,直接出列。(图中三的“Q”)
    3.延位找到(本字符不动,在对面的后几位找到)。(图三中,B字串中的“E”越过了字串A的“BCD”),该不该连线呢?这正是这个主题的难点。我借助于解 S1、S2、S3、S4的“LCS”问题的方法(递归)来解决。
    “中文打字测验”大量的情况就是第1种。所以近千字的文本能在1秒钟“批完”(我试过近百字的、毫不相干的两个文本,慢极了,最后还“没有响应”,只能Ctrl-Break 中断)。

本博文的第3个插图看起来比较杂乱、费劲。谨请见谅。要强调说明,我的思路是,以下面一行的字串的每个字来判断,因此要把上下2行交换后再算一次,2次结果如有不同,应该取其中较大的结果作为“最长公共子序列”。

请注意:图中提到的“S1、S4”如何取出是个“难点”,这里有几点要求:

1.红色 S2、S3 好理解,它们的“首字符”就是“正相遇”的、待判定的那个字符。(图三中,B字串中的“E”)
2.★重点是蓝色 S1与S4的“首字符”必须相同。(我是用双重 FOR 来寻找和取出的)。

以上是本人的一点肤浅的看法,程序会有错误和不妥,欢迎指正。如你发现程序结果有错,请在留言中告知,真诚感谢。

我在9月11日对上面的博文有以下更正:

因为程序有错,所以在交换上下字符串后运算结果不同。其实2次的长度应该是一样的,串的内容可能会有不同。我把程序更正了一下。换了附件程序,也换了上面的程序结果的截图。并在此向读者表示深深的歉意。

文章评论,共0条
游客请输入验证码
浏览51804次
文章分类