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

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 Hash(string terminalPhrase) {
      return terminalPhrase;
    }
  }
}