c# - Longest Unique Palindromes -
i have following interface
public interface ipalindromeengine { palindrome getlongestpalindrome(string sequence); task<palindrome> getlongestpalindromeasync(string sequence); list<palindrome> getlongestpalindromes(string sequence, int n, bool uniqueonly); task<list<palindrome>> getlongestpalindromesasync(string sequence, int n, bool uniqueonly); } with implementation taken http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html code seems tested (from commenters , implementers)...
/// <summary> /// computes longest palindromic substring in linear time /// using manacher's algorithm. /// /// code lifted following excellent reference /// http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html /// </summary> public class manacherpalindromeengine : ipalindromeengine { // p[i] = length of longest palindromic substring of transform, centered @ i. private int[] p; private char[] transform; private string sequence; private void initialize() { transform = new char[sequence.length * 2 + 3]; transform[0] = '$'; transform[sequence.length * 2 + 2] = '@'; (int = 0; < sequence.length; ++i) { transform[2 * + 1] = '#'; transform[2 * + 2] = sequence[i]; } transform[sequence.length * 2 + 1] = '#'; } private void extractpalindromesviamanacher(string sequence) { this.sequence = sequence; initialize(); int center = 0, right = 0; p = new int[transform.length]; (int = 1; < transform.length - 1; i++) { int mirror = 2 * center - i; if (right > i) p[i] = math.min(right - i, p[mirror]); // attempt expand palindrome centered @ i. while (transform[i + (1 + p[i])] == transform[i - (1 + p[i])]) p[i]++; // if palindrome centered @ expands past right, // adjust center based on expanded palindrome. if (i + p[i] > right) { center = i; right = + p[i]; } } } public palindrome getlongestpalindrome(string sequence) { if (string.isnullorempty(sequence)) return null; extractpalindromesviamanacher(sequence); int length = 0; int center = 0; (int = 1; < p.length - 1; ++i) { if (p[i] > length) { length = p[i]; center = i; } } int startindex = (center - 1 - length) / 2; string s = this.sequence.substring(startindex, length); return new palindrome(s, startindex); } public task<palindrome> getlongestpalindromeasync(string sequence) { return task.run(() => getlongestpalindrome(sequence)); } public list<palindrome> getlongestpalindromes(string sequence, int n, bool uniqueonly) { if (string.isnullorempty(sequence)) return null; extractpalindromesviamanacher(sequence); list<palindrome> palindromes = null; if (uniqueonly) { palindromes = p .select((l, i) => new { length = l, index = }) .orderbydescending(c => c.length) .select(c => { int startindex = (c.index - 1 - c.length) / 2; string s = this.sequence.substring(startindex, c.length); trace.writeline(startindex); return new palindrome(s, startindex); }) .tolist(); palindromes = palindromes .distinct(new palindrome.duplicatecomparer()) .take(n) .tolist(); } else { palindromes = p .select((l, i) => new { length = l, index = }) .orderbydescending(c => c.length) .take(n) .select(c => { int startindex = (c.index - 1 - c.length) / 2; string s = this.sequence.substring(startindex, c.length); trace.writeline(startindex); return new palindrome(s, startindex); }) .tolist(); } return palindromes; } public task<list<palindrome>> getlongestpalindromesasync(string sequence, int n, bool uniqueonly) { return task.run(() => getlongestpalindromes(sequence, n, uniqueonly)); } } with
public class palindrome { public palindrome(string sequence, int startindex) { sequence = sequence; if (startindex < 0) throw new argumentexception("startindex must >= 0"); startindex = startindex; } public int startindex { get; set; } public int length { { if (string.isnullorempty(sequence)) return 0; return sequence.length; } } public string sequence { get; } internal class duplicatecomparer : iequalitycomparer<palindrome> { public bool equals(palindrome x, palindrome y) { return x.sequence == y.sequence; } public int gethashcode(palindrome obj) { unchecked { int hash = 17; return hash * 23 + obj.sequence.gethashcode(); } } } } now have tested on number of test cases, 1 case not seem right. input string
"weeewweeew"
this returns results:
- weeewweeew start: 0 length: 10
- weeew start: 0 length: 5
ee start: 1 length: 2
why aren't getting string "eeewweee" or "eee"?
any other suggestions on code quality appreciated.
palindromes = p .select((l, i) => new { length = l, index = }) .orderbydescending(c => c.length) at point, every position in string, query contains length of longest palindrome centered @ position. in order retrieve all palindromes, need select of palindrome's substrings same center:
.selectmany(c => { int startindex = (c.index - 1 - c.length) / 2; int numsubpalindromes = (c.length + 1) / 2; palindrome[] subpalindromes = new palindrome[numsubpalindromes]; (int = 0; < numsubpalindromes; ++i) { string s = this.sequence.substring(startindex + i, c.length - * 2); subpalindromes[i] = new palindrome(s, startindex + i); } return subpalindromes; }) .tolist();
Comments
Post a Comment