algorithm - 字符串中的子字符串及其反转

Question

我的教授在动态编程课上谈到了这个问题，并要求我们考虑一下。她也给我们举了一些例子。给定一个字符串，我们要找到最长的连续子序列，其反向也是给定字符串中存在的子序列。

例子:

INPUT: pqrstuvtsrv
OUTPUT: i=3, k=2

rst -> tsr (rst found first at i=3 and for 2 more positions)

INPUT: mpqrsrqp
OUTPUT: i=2, k=6
pqrsrqp in reverse

INPUT: mmpqssss
OUTPUT: i=5, k=3

我想将字符串及其反转放入 2 个不同的数组中，然后逐个字符进行比较。但我确信这不是最好的方法。关于什么是最有效的，有什么建议吗？

Answer 1

这是 Longest common substring problem 的变体.您正在寻找输入及其反向的最长公共(public)子串。

对于这种特定情况，可能有更简单的解决方案，但目前我对此表示怀疑。 =)