子串和字符串中的反 [英] Substring and its reverse in a string

问题描述

我的教授在谈论这在动态编程类，并要求我们考虑它。她给了我们一些例子也是如此。给定一个字符串，我们要找到持续时间最长的序列，其反过来也是一个序列present给定的字符串中的

My professor was talking about this in a Dynamic programming class and asked us to think over it. She gave us some examples as well. Given a string, we were to find the longest continuous subsequence whose reverse is also a subsequence present in the given string.

例如：

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个不同的阵列和性格比较字符的。但我敢肯定这是不是做到这一点的最好办法。任何建议，这可能是最有效的？

I thought of putting the string and its reverse into 2 different arrays and comparing character by character. But I'm sure this is not the best way to do it. Any suggestions as to what could be the most efficient ?

推荐答案

这是对最长公共子问题的。您正在寻找您的投入和其反向的最长公共子串。

This is a variation on the Longest common substring problem. You are looking for the longest common substring of your input and its reverse.

有可能是这种特定的情况下，一个简单的解决方案，但就目前而言，我对此表示怀疑。 =）

There may be a simpler solution for this specific case, but for the moment, I doubt it. =)

这篇关于子串和字符串中的反的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！