编写一个函数，返回给定字符串中最长的回文 [英] Write a function that returns the longest palindrome in a given string

问题描述

例如字符串abaccddccefe"中的ccddcc"

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

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

I thought of a solution but it runs in O(n^2) time

算法 1:

步骤:这是一种蛮力方法

Steps: Its a brute force method

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

问题:1. 这个算法在 O(n^2) 时间内运行.

Issues: 1. This algo runs in O(n^2) time.

算法 2:

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

你们能想出一种在更好的时间运行的算法吗?如果可能的话 O(n) 时间

Can you guys think of an algo which runs in a better time. If possible O(n) time

推荐答案

您可以使用 O(n) 时间内的 >Manacher 算法！它的实现可以在这里和这里.

You can find the the longest palindrome using Manacher's Algorithm in O(n) time! Its implementation can be found here and here.

对于输入 String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" 它会找到正确的输出 1234567887654321.

For input String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" it finds the correct output which is 1234567887654321.

这篇关于编写一个函数，返回给定字符串中最长的回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！