有没有计算两个给定字符串的最长公共回文子序列长度的有效算法？
例如：
字符串1。afbcdfca
字符串2。bcadfcgyfka
lcps是5，lcps字符串是afcfa。
最佳答案
对。
只需对两个以上的序列使用lcs算法。
如果我没弄错的话
LCS( afbcdfca, acfdcbfa, bcadfcgyfka, akfygcfdacb) = afcfa
这取决于你找出字符串2和字符串4。
更新：不，这里有一个反例：lcs（a ba，aba，bab，bab）=ab，ba。lcs不能确保子序列是回文，您可能需要添加此约束。无论如何，lcs的递推方程是一个很好的起点。
如果在生成器样式中实现lcs，以便它生成长度为n、然后是n-1、n-2等的所有lcs，那么您应该能够相当高效地计算lcs gen（string1，reverse-string1）、lcs gen（string2，reverse-string2）中最长的公共成员。但我还没有检查，是否有一个高效的lcs-gen。