source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs @ 11857

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 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<Feature> 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();
    }
  }
}