如何在一串字符中显示最长的回文？ [英] how to display the longest palindrome in a string of characters?

问题描述

我的一位朋友在ACHERON的技术访谈中遇到了这个问题。提问者要求显示给定字符串中最长的回文。

例如：nitinwearsottoeverytime - 没有空格。

其中nitin和otto是两个可能的回文，因为nitin是5个字符且很长，它必须显示出来。

执行此操作的代码是什么？

解释清除这个的逻辑！

解决方案

你可以在O（n）时间内使用Manacher算法找到最长的回文！它的实现可以在这里找到

输入字符串s = HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE。它找到了正确的输出，即1234567887654321。

为了更好地解释在线性时间内解决这个问题的逻辑：[ ^ ]。



对于C＃中的许多实现： [ ^ ]。

one of my friend encountered this question in ACHERON's technical interview.the questioner had asked to display the longest palindrome in a given string.
for example:"nitinwearsottoeverytime"-no spaces.
where nitin and otto are the two possible palindrome and since nitin is 5characters and long,it must bedisplayed.
what is the code to perform this?
do explain the logic to clear this!

解决方案

You can find the the longest palindrome using Manacher's Algorithm in O(n) time! Its implementation can be found here
For input String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE". It finds the correct output which is 1234567887654321.

For a good explanation of the logic in solving this problem in linear time: [^].

For many implementations in C#: [^].

这篇关于如何在一串字符中显示最长的回文？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！