最长回文子序列(LCS)

xiaoxiao2021-02-28  79

想不通为什么,当个结论记住:

把一个字符串逆序后和原字符串进最长公共子序列,可以计算出它的最长回文串长度。 计算出的最长公共子序列不一定是最长回文子序列。 例如: kfclbckibbibjccbej jebccjbibbikcblcfk bcibbibc是他们的LCS,但是却不是回文串

但是它的前len/2个一定是回文串的前半部分 知道了前len/2,就可以直接构造出回文串的后半部分了 要注意长度的奇偶性问题

转载请注明原文地址: https://www.6miu.com/read-79393.html

最新回复(0)