using System; using System.Collections.Generic; using System.Linq; using System.Text; using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; namespace HeuristicLab.Problems.GrammaticalOptimization { public class PalindromeProblem : ISymbolicExpressionTreeProblem { // length of the longest palindrome in the sentence private const string grammarString = @" G(S): S -> T | TS T -> a .. z "; private const string hlGrammarString = @" G(S): S -> a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | SS "; private readonly IGrammar grammar; public string Name { get { return "Palindrome"; } } public PalindromeProblem() { this.grammar = new Grammar(grammarString); this.TreeBasedGPGrammar = new Grammar(hlGrammarString); } 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 phrase) { return phrase; } public IEnumerable GetFeatures(string phrase) { throw new NotImplementedException(); } public IGrammar TreeBasedGPGrammar { get; private set; } public string ConvertTreeToSentence(ISymbolicExpressionTree tree) { var sb = new StringBuilder(); foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) { if (s.Symbol.Name == "S") continue; sb.Append(s.Symbol.Name); } return sb.ToString(); } } }