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

Last change on this file since 11727 was 11727, checked in by gkronber, 5 years ago

#2283: worked on grammatical optimization problem solvers (simple MCTS done)

File size: 2.1 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5
6namespace HeuristicLab.Problems.GrammaticalOptimization {
7  public class PalindromeProblem : IProblem {
8    // length of the longest palindrome in the sentence
9    private const string grammarString = @"
10G(S):
11S -> T | TS
12T -> a .. z
13";
14
15    private readonly IGrammar grammar;
16    public PalindromeProblem() {
17      this.grammar = new Grammar(grammarString);
18    }
19
20    public double GetBestKnownQuality(int maxLen) {
21      // the whole sentence is a palindrome
22      return maxLen;
23    }
24
25    public IGrammar Grammar {
26      get { return grammar; }
27    }
28
29    public double Evaluate(string sentence) {
30      return LongestPalindromicSubstring(sentence).Length;
31    }
32
33
34    private static string Preprocess(string s) {
35      var t = new char[2 * s.Length + 3];
36      t[0] = '$';
37      t[t.Length - 2] = '#';
38      t[t.Length - 1] = '@';
39      for (int i = 0; i < s.Length; i++) {
40        t[2 * (i) + 1] = '#';
41        t[2 * i + 2] = s[i];
42      }
43
44      return new string(t);
45    }
46
47    public static string LongestPalindromicSubstring(string str) {
48      var tLen = 2 * str.Length + 3;
49      var p = new int[tLen];
50      var t = Preprocess(str);
51
52      var center = 0;
53      var right = 0;
54      for (int i = 1; i < t.Length - 1; i++) {
55        var mirror = 2 * center - i;
56        if (right > i) p[i] = Math.Min(right - i, p[mirror]);
57        while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) {
58          p[i]++;
59        }
60        if (i + p[i] > right) {
61          center = i;
62          right = i + p[i];
63        }
64      }
65      var len = 0;
66      center = 0;
67      for (int i = 0; i < t.Length - 1; i++) {
68        if (p[i] > len) {
69          center = i;
70          len = p[i];
71        }
72      }
73
74      var start = (center - 1 - len) / 2;
75      var result = new StringBuilder();
76      for (int i = 0; i < len; i++) {
77        result.Append(str[start + i]);
78      }
79      return result.ToString();
80    }
81
82    public string Hash(string terminalPhrase) {
83      return terminalPhrase;
84    }
85  }
86}
Note: See TracBrowser for help on using the repository browser.