javascript实现最长公共子序列实例代码(4)

0 B 0

然后我们让Y多出一个D做帮手,{"",A,B,AB} vs {"",B,D,BD},显然,继续填1. 一直填到Y的第二个B之前,都是1。 因为到BDCAB时,它们有另一个公共子序列,AB。

x "" B D C A B A
"" 0 0 0 0 0 0 0
A 0 0 0 0 1 1 1
B 0 1 1 1 1 2
C 0
D 0
A 0
B 0

到这一步,我们可以总结一些规则了,之后就是通过计算验证我们的想法,加入新的规则或限定条件来完善。

Y将所有字符派上去,X依然是2个字符,经仔细观察,还是填2.

看五行,X再多派一个C,ABC的子序列集合比AB的子序列集合大一些,那么它与Y的B子序列集合大一些,就算不大,就不能比原来的小。显然新增的C不能成为战力,不是两者的公共字符,因此值应该等于AB的子序列集合。

× "" B D C A B A
"" 0 0 0 0 0 0 0
A 0 0 0 0 1 1 1
B 0 1 1 1 1 2 2
C 0 1
D 0
A 0
B 0

并且我们可以确定,如果两个字符串要比较的字符不一样,那么要填的格子是与其左边或上边有关,那边大就取那个。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/470.html