Find the longest palindromes

A clear explanation and solution in (Python, Java, C++):

<http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/>

the most naive solution would be to exhaustively examine all n (n + 1) / 2 substrings of the givenn-length string, test each one if it's a palindrome, and keep track of the longest one seen so far. This has worst-case complexity O(n³), but we can easily do better by realizing that a palindrome is centered on either a letter (for odd-length palindromes) or a space between letters (for even-length palindromes). Therefore we can examine all 2n + 1 possible centers and find the longest palindrome for that center, keeping track of the overall longest palindrome. This has worst-case complexity O(n²).

But this can be done in O(N)

SomeLinks:

http://stackoverflow.com/questions/2677000/how-to-find-the-longest-palindrome-in-a-given-string

http://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string

http://johanjeuring.blogspot.com/2007/08/finding-palindromes.html

A Java Code:

est data used is HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE

  public static string GetPalindromeString(string theInputString) 

{ int j = 0;

          int k = 0;         string aPalindrome = string.Empty;         string aLongestPalindrome = string.Empty ;                   for (int i = 1; i < theInputString.Length; i++)         {             k = i + 1;             j = i - 1;             while (j >= 0 && k < theInputString.Length)             {                 if (theInputString[j] != theInputString[k])                 {                     break;                 }                 else                 {                     j--;                     k++;                 }                 aPalindrome = theInputString.Substring(j + 1, k - j - 1);                 if (aPalindrome.Length > aLongestPalindrome.Length)                 {                     aLongestPalindrome = aPalindrome;                 }             }         }         return aLongestPalindrome;        }

This one is related -- to use the regular expression to detect the palindrome:

http://stackoverflow.com/questions/233243/how-to-check-that-a-string-is-a-palindrome-using-regular-expressions

--

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥