using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace HeuristicLab.Problems.GrammaticalOptimization { public class PalindromeProblem : IProblem { // length of the longest palindrome in the sentence private const string grammarString = @" G(S): S -> T | TS T -> a .. z "; private readonly IGrammar grammar; public PalindromeProblem() { this.grammar = new Grammar(grammarString); } public double BestKnownQuality(int maxLen) { // the whole sentence is a palindrome return maxLen; } public IGrammar Grammar { get { return grammar; } } public double Evaluate(string sentence) { return LongestPalindromicSubstring(sentence).Length; } private static string Preprocess(string s) { var t = new char[2 * s.Length + 3]; t[0] = '$'; t[t.Length - 2] = '#'; t[t.Length - 1] = '@'; for (int i = 0; i < s.Length; i++) { t[2 * (i) + 1] = '#'; t[2 * i + 2] = s[i]; } return new string(t); } public static string LongestPalindromicSubstring(string str) { var tLen = 2 * str.Length + 3; var p = new int[tLen]; var t = Preprocess(str); var center = 0; var right = 0; for (int i = 1; i < t.Length - 1; i++) { var mirror = 2 * center - i; if (right > i) p[i] = Math.Min(right - i, p[mirror]); while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) { p[i]++; } if (i + p[i] > right) { center = i; right = i + p[i]; } } var len = 0; center = 0; for (int i = 0; i < t.Length - 1; i++) { if (p[i] > len) { center = i; len = p[i]; } } var start = (center - 1 - len) / 2; var result = new StringBuilder(); for (int i = 0; i < len; i++) { result.Append(str[start + i]); } return result.ToString(); } public string CanonicalRepresentation(string terminalPhrase) { return terminalPhrase; } } }