algorithm - 编写一个函数，返回给定字符串中最长的回文

Question

e.g "ccddcc" in the string "abaccddccefe"

我想到了一个解决方案，但它在 O(n^2) 时间内运行

算法 1:

步骤: 这是一种蛮力方法

1. 有2个for循环
   for i = 1 to i 小于 array.length -1
   对于 j=i+1 到 j 小于 array.length
2. 这样你就可以从数组中得到所有可能组合的子串
3. 有一个回文函数来检查一个字符串是否是回文
4. 因此对于每个子串 (i,j) 调用此函数，如果它是回文，则将其存储在字符串变量中
5. 如果找到下一个回文子串并且它大于当前回文子串，则将其替换为当前回文子串。
6. 最后你的字符串变量会有答案

问题: 1. 该算法运行时间为 O(n^2)。

算法 2:

1. 反转字符串并将其存储在不同的数组中
2. 现在找到两个数组之间最大的匹配子串
3. 但这也是在 O(n^2) 时间内运行

你们能想出一个运行时间更好的算法吗？如果可能 O(n) 时间

Answer 1

您可以在 O(n) 时间内使用 Manacher's Algorithm 找到最长的回文!它的实现可以在 here 和 here 中找到。

对于输入 String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"，它找到正确的输出，即 1234567887654321。