如ccddcc中的字符串abaccddccefe

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

有2环 对于i = 1到i小于array.length -1 对于j = i + 1的到j小于array.length 这样，您就可以得到每一个可能的组合的字符串从数组 有一个回文功能，它检查一个字符串是否是回文 让每一个子（I，J）调用这个函数，如果它是一个回文其存储在一个字符串变量 如果你发现下一个回文子串，如果是大于当前之一，目前进行更换。 在最后的字符串变量将有答案 Have 2 for loops for i = 1 to i less than array.length -1 for j=i+1 to j less than array.length This way you can get substring of every possible combination from the array Have a palindrome function which checks if a string is palindrome so for every substring (i,j) call this function, if it is a palindrome store it in a string variable If you find next palindrome substring and if it is greater than the current one, replace it with current one. Finally your string variable will have the answer

问题： 1.本算法中为O（N ^ 2）的时间。

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

算法中2：

反转字符串，并将其存储在diferent阵列 现在，发现无论是阵列之间的最大匹配子 然而，这也为O（N ^ 2）时间 Reverse the string and store it in diferent array Now find the largest matching substring between both the array But this too runs in O(n^2) time

你们可以认为它运行在一个更好的时间的算法中的。如果可能的话O（n）的时间

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

推荐答案

您可以用找到的最长的回文的 Manacher的算法 在 O（N）的时间！它的实施可以发现这里和的