using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace HeuristicLab.Problems.GrammaticalOptimization { public class HardPalindromeProblem : IProblem { // length of the longest palindrome in the sentence + number of different symbols occurring in the palindrome private const string grammarString = @" G(S): S -> T | TS T -> a .. z "; private readonly IGrammar grammar; public HardPalindromeProblem() { this.grammar = new Grammar(grammarString); } public double BestKnownQuality(int maxLen) { // the whole sentence is a palindrome + each symbol occurs only once or twice // for odd total length the number of different characters can be larger than len/2 (aba) // the second part is limited to 26 different characters return maxLen + Math.Min(26, (maxLen + 1) / 2); } public IGrammar Grammar { get { return grammar; } } public double Evaluate(string sentence) { var palindrome = PalindromeProblem.LongestPalindromicSubstring(sentence); var palindromeBytes = ASCIIEncoding.ASCII.GetBytes(palindrome); var chrCount = new int[256]; foreach (var b in palindromeBytes) { chrCount[b]++; } return palindrome.Length + chrCount.Count(c => c > 0); } public string CanonicalRepresentation(string terminalPhrase) { return terminalPhrase; } } }