使用后缀树可以解决最长的公共子序列吗？

Question

是否有可能使用后缀树来解决最长的公共子序列？

我想解决一个最长的公共子序列是否可以使用后缀树来解决？

Answer 1

后缀树用于查找最长的公共前缀，后缀树是后缀树中最低的共同祖先。唯一需要数据结构来查找两个字符串中最长的公共子序列的方法是，当您实现动态编程解决方案时，该解决方案使用二维数组来跟踪解决问题的结果。