再说说“LCS”的算法-----分析我的博文(2022-12-09)插图上部的那条【绿色横线】区域

作者在 2023-02-07 16:18:38 发布以下内容
前一个公共子串结束后,上下两个字(位置是n1和n2)不相同,并且在n1的右面找到了与n2相同的字(图一中的“罗”--“罗”)。(插图二)里“上部的那条绿色横线”就表示:从n1(含n1)到“罗”之前(n1+r-1)(不含“罗”)的那个区域。这是一个关键区域。
我是这样分析的:如果下面的“罗”字因为不符合“最长”的缘故而不保留的话,那么在txt1(上面的字符串)里,★“最优的公共子串首字”一定在那个区域内(英白)!(因为,如果2个字都在“罗”的★右面(红色横线里),怎么可能比‘罗--罗’更长呢?)
于是,通过双重(For)循环和调用函数必然可以在“两条绿色横线”内找到“最优的公共子串首字”,于是,下面的“罗”字出列【③2】。反之,如果在这个区域内找不到(蓝蓝)>(红红),下面的“罗”字就留下【③1】。★这是求解“LCS”过程中唯一需要复杂判断的地方。通过简单的①、②和复杂的③1、③2来判定公共子串的“首字”是哪一个以后,★公共子串“首字”后面的字,都可以用“情况①”来简单判定为“保留”了。


默认分类 | 阅读 1063 次
文章评论,共0条
游客请输入验证码
浏览96245次
文章分类