Geek Answers Handbook

How to find the longest palindrome in a given line?

Possible duplicate:
Write a function that returns the longest palindrome in a given string

I know how to do this in O (n ^ 2). But there seems to be a better solution.

I found this one , and there is a link to the O (n) answer, but it is written in Haskell and is not clear to me.

It would be great to get an answer in C # or the like.

+2
source share
6 answers

I found a clear explanation of the solution here . Thanks to Justin for this link.

There you can find implementations of Python and Java algorithm (C ++ implementation contains errors).

And here is the C # implementation, which is just a translation of these algorithms.

public static int LongestPalindrome(string seq) { int Longest = 0; List<int> l = new List<int>(); int i = 0; int palLen = 0; int s = 0; int e = 0; while (i<seq.Length) { if (i > palLen && seq[i-palLen-1] == seq[i]) { palLen += 2; i += 1; continue; } l.Add(palLen); Longest = Math.Max(Longest, palLen); s = l.Count - 2; e = s - palLen; bool found = false; for (int j = s; j > e; j--) { int d = j - e - 1; if (l[j] == d) { palLen = d; found = true; break; } l.Add(Math.Min(d, l[j])); } if (!found) { palLen = 1; i += 1; } } l.Add(palLen); Longest = Math.Max(Longest, palLen); return Longest; }
+5
source

And this is his java version:

 public static int LongestPalindrome(String seq) { int Longest = 0; List<Integer> l = new ArrayList<Integer>(); int i = 0; int palLen = 0; int s = 0; int e = 0; while (i < seq.length()) { if (i > palLen && seq.charAt(i - palLen - 1) == seq.charAt(i)) { palLen += 2; i += 1; continue; } l.add(palLen); Longest = Math.max(Longest, palLen); s = l.size() - 2; e = s - palLen; boolean found = false; for (int j = s; j > e; j--) { int d = j - e - 1; if (l.get(j) == d) { palLen = d; found = true; break; } l.add(Math.min(d, l.get(j))); } if (!found) { palLen = 1; i += 1; } } l.add(palLen); Longest = Math.max(Longest, palLen); return Longest; }
+1
source

I recently wrote the following code during an interview ...

  public string FindMaxLengthPalindrome(string s) { string maxLengthPalindrome = ""; if (s == null) return s; int len = s.Length; for(int i = 0; i < len; i++) { for (int j = 0; j < len - i; j++) { bool found = true; for (int k = j; k < (len - j) / 2; k++) { if (s[k] != s[len - (k - j + 1)]) { found = false; break; } } if (found) { if (len - j > maxLengthPalindrome.Length) maxLengthPalindrome = s.Substring(j, len - j); } if(maxLengthPalindrome.Length >= (len - (i + j))) break; } if (maxLengthPalindrome.Length >= (len - i)) break; } return maxLengthPalindrome; }
+1
source

I had a question when I interviewed.

I found out when I got home, unfortunately.

 public static string GetMaxPalindromeString(string testingString) { int stringLength = testingString.Length; int maxPalindromeStringLength = 0; int maxPalindromeStringStartIndex = 0; for (int i = 0; i < testingString.Length; i++) { int currentCharIndex = i; for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--) { bool isPalindrome = true; if (testingString[currentCharIndex] != testingString[lastCharIndex]) { continue; } for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < lastCharIndex / 2; nextCharIndex++) { if (testingString[nextCharIndex] != testingString[lastCharIndex - 1]) { isPalindrome = false; break; } } if (isPalindrome) { if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength) { maxPalindromeStringStartIndex = currentCharIndex; maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex; } } break; } } return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength); }
+1
source 
 public static string GetMaxPalindromeString(string testingString) { int stringLength = testingString.Length; int maxPalindromeStringLength = 0; int maxPalindromeStringStartIndex = 0; for (int i = 0; i < stringLength; i++) { int currentCharIndex = i; for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--) { if (lastCharIndex - currentCharIndex + 1 < maxPalindromeStringLength) { break; } bool isPalindrome = true; if (testingString[currentCharIndex] != testingString[lastCharIndex]) { continue; } else { int matchedCharIndexFromEnd = lastCharIndex - 1; for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < matchedCharIndexFromEnd; nextCharIndex++) { if (testingString[nextCharIndex] != testingString[matchedCharIndexFromEnd]) { isPalindrome = false; break; } matchedCharIndexFromEnd--; } } if (isPalindrome) { if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength) { maxPalindromeStringStartIndex = currentCharIndex; maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex; } break; } } } if(maxPalindromeStringLength>0) { return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength); } return null; }
+1
source

WITH#

At first I even look for length palindromes. Then I look for the odd palindromes. When he finds a palindrome, he determines the length and sets the maximum length accordingly. The average complexity of this case is linear.

  protected static int LongestPalindrome(string str) { int i = 0; int j = 1; int oldJ = 1; int intMax = 1; int intCount = 0; if (str.Length == 0) return 0; if (str.Length == 1) return 1; int[] intDistance = new int[2] {0,1}; for( int k = 0; k < intDistance.Length; k++ ){ j = 1 + intDistance[k]; oldJ = j; intCount = 0; i = 0; while (j < str.Length) { if (str[i].Equals(str[j])) { oldJ = j; intCount = 2 + intDistance[k]; i--; j++; while (i >= 0 && j < str.Length) { if (str[i].Equals(str[j])) { intCount += 2; i--; j++; continue; } else { break; } } intMax = getMax(intMax, intCount); j = oldJ + 1; i = j - 1 - intDistance[k]; } else { i++; j++; } } } return intMax; } protected static int getMax(int a, int b) { if (a > b) return a; return b; }
0
source

More articles:


All Articles