回文(C#)

問題はこちら。
http://qiita.com/Nabetani/items/0b56395d4c9e7c64b230

全部同じ文字だと、ペアの数が増えるので、包括関係の判断が少し重い。
包括関係を解析する際に、厳密な親子関係を確認設定した方が、軽いかな。

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ord15
{
    class Program
    {
        class Pair
        {
            public int start;
            public int end;
            public char ch;

            public int level;
            public List<Pair> includes = new List<Pair>();
            public List<Pair> included = new List<Pair>();

            public Pair link;
            public String pattern;

            public bool canInclude(Pair p)
            {
                return start < p.start && end > p.end;
            }

        }

        static int solve(String str)
        {
            // 位置を計算
            Dictionary<char, List<int>> positions = new Dictionary<char, List<int>>();
            for (int i = 0; i < str.Length; i++)
            {
                char ch = str[i];

                if (!positions.ContainsKey(ch))
                    positions[ch] = new List<int>();
                positions[ch].Add(i);
            }

            // pairを作成
            List<Pair> pairs = new List<Pair>();
            foreach (var unit in positions)
            {
                var ch = unit.Key;
                var positionList = unit.Value; 
                for (int i = 0; i < positionList.Count - 1; i++)
                {
                    for (int j = i + 1; j < positionList.Count; j++)
                    {
                        pairs.Add(new Pair { start = positionList[i], end = positionList[j], ch = ch });
                    }
                }
            }

            // ペアなしの確認
            if (pairs.Count == 0)
                return 1;

            // 包括関係の設定
            for (int i = 0; i < pairs.Count; i++)
            {
                for (int j = 0; j < pairs.Count; j++)
                {
                    if (i == j)
                        continue;

                    if (pairs[i].canInclude(pairs[j]))
                    {
                        pairs[i].includes.Add(pairs[j]);
                        pairs[j].included.Add(pairs[i]);
                    }
                }
            }

            // 処理キューの作成
            // 選択削除を可能とするために、QueueでなくListを用いる
            List<Pair> queue = new List<Pair>();

            // 子供を持たないものをキューに入れる
            // 隣接から
            pairs.Where(x => x.includes.Count == 0 && x.start == x.end - 1).ToList().ForEach(x =>
            {
                x.level = 2;
                x.pattern = "" + x.ch + x.ch;
                queue.Add(x);
            });
            // 包括
            pairs.Where(x => x.includes.Count == 0 && x.start != x.end - 1).ToList().ForEach(x =>
            {
                x.level = 3;
                x.pattern = "" + x.ch + str[x.start + 1] + x.ch;
                queue.Add(x);
            });

            // 親にプロパゲートしていく
            while (queue.Count > 0)
            {
                var pair = queue[0];
                queue.RemoveAt(0);
                pair.included.ForEach(x =>
                {
                    x.level = pair.level + 2;
                    x.link = pair;
                    x.pattern = x.ch + pair.pattern + x.ch;

                    // 新しく追加する場合は、前の要求は削除
                    // これがないと、オーバーヘッドがかなり大きい
                    queue.Remove(x);
                    queue.Add(x);
                });
            }

            // 最大文字列のデバッグ出力
            var maxOne = pairs.OrderBy(x => x.level).Last();
            System.Diagnostics.Debug.WriteLine("{0} => {1}({2})", str, maxOne.level, maxOne.pattern);

            // 最大長を取る
            return maxOne.level;
        }

        static void test(String str, String result)
        {
            var actual = solve(str).ToString();
            System.Diagnostics.Debug.Assert(result == actual, "str:" + str + ", expected:" + result + " actual:" + actual);
        }

        static void Main(string[] args)
        {
            /*0*/
            test("I_believe_you_can_solve", "9");
            /*1*/
            test("a", "1");
            /*2*/
            test("aa", "2");
            /*3*/
            test("aaa", "3");
       }
    }
}