find longest palindrome

FindLongestPalindrome.cs

using System.Text;
using System;
using System.Diagnostics;

namespace ConsoleApplication15
{
    class Program
    {
        static void Main(string[] args)
        {
            Main_Profiling(args);
        }

        static void Main_test(string[] args)
        {
            string A;

            A = "abcde";
            Debug.Assert((new FindPal(A)).Solve().Equals(new Tuple<int, int>(0, 0)));

            A = "abcba";
            Debug.Assert((new FindPal(A)).Solve().Equals(new Tuple<int, int>(0, 4)));

            A = "1abccba2";
            Debug.Assert((new FindPal(A)).Solve().Equals(new Tuple<int, int>(1, 6)));

            A = "1abccba22aa";
            Debug.Assert((new FindPal(A)).Solve().Equals(new Tuple<int, int>(1, 6)));

            A = "1";
            Debug.Assert((new FindPal(A)).Solve().Equals(new Tuple<int, int>(0, 0)));

            A = "";
            Debug.Assert((new FindPal(A)).Solve() == null);

            Console.Read();
        }

        static void Main_Profiling(string[] args)
        {
            foreach (var N in new int[] { 100, 1000, 10000, 100000, 1000000 })
            {
                var B = new StringBuilder();
                for (int i = 0; i < N; i++)
                {
                    B.Append('a');
                }
                var A = B.ToString();
                var timer = new Stopwatch();
                Tuple<int, int> res = null;
                int M = 50;
                for (int i = 0; i < M; i++)
                {
                    timer.Start();
                    res = (new FindPal(A)).Solve();
                    timer.Stop();
                }
                Console.WriteLine("result: {0}, {1}", res.Item1, res.Item2);
                Console.WriteLine("N = {0}, ave time elapsed: {1}", N, timer.ElapsedTicks / (double)M);
            }
            Console.Read();
        }
    }

    class FindPal
    {
        public string A;
        public Tuple<int,bool>[] table;   // {PalStartPos, IsRepeatedChars}
        public FindPal(string A)
        {
            this.A = A;
            this.table = new Tuple<int, bool>[A.Length];
            for (int i = 0; i < A.Length; i++)
            {
                table[i] = null;
            }
        }
        private Tuple<int, bool> F(int i)
        {
            if (table[i] != null)
                return table[i];
            if (i == 0)
                table[i] = new Tuple<int, bool>(i, true);
            else if (F(i - 1).Item1 >= 1 && A[F(i - 1).Item1 - 1] == A[i])
                table[i] = new Tuple<int, bool>(F(i - 1).Item1 - 1, false);
            else if (F(i - 1).Item2 && A[F(i - 1).Item1] == A[i])
                table[i] = new Tuple<int, bool>(F(i - 1).Item1, true);
            else
                table[i] = new Tuple<int, bool>(i, true);
            return table[i];
        }

        public Tuple<int, int> Solve()
        {
            if (A.Length == 0) return null;
            int m1 = -1, m2 = -1, l = 0;
            for (int i = 0; i < A.Length; i++)
            {
                int b = F(i).Item1;
                int l_ = i - b + 1;
                if (l_ > l)
                {
                    l = l_;
                    m1 = b;
                    m2 = i;
                }
            }
            return new Tuple<int, int>(m1, m2);
        }
    }
}