题解 | #密码截取#

using System;
using System.Runtime.InteropServices;

namespace HJ32
{

    /// <summary>
    /// 密码截取/最长的回字符串字串
    /// </summary>
    internal class Program
    {
        static void Main(string[] args)
        {
            var strInput = Console.ReadLine();

            int count = GetPalindromeMaxCount01(strInput);
            //int count = GetPalindromeMaxCount02(strInput);

            Console.WriteLine(count);

        }

        /// <summary> 中心扩散法：以每一个字符为中心，向两边扩散，求最大回文串长度 </summary>
        static int GetPalindromeMaxCount01(string str)
        {
            if (string.IsNullOrEmpty(str))
            {
                return 0;
            }
            var chars = str.ToCharArray();
            int maxCount = 0;
            int length = chars.Length;

            //中心扩散法
            for (int i = 0; i < length; i++)
            {
                int left = i - 1;
                int right = i + 1;
                //ABA型
                while (true)
                {
                    if (left >= 0 && right < length && chars[left] == chars[right])
                    {
                        if (right - left + 1 > maxCount)
                        {
                            maxCount = right - left + 1;
                        }
                        //继续扩散，尝试取得最大长度
                        left--;
                        right++;
                    }
                    else
                    {
                        break;
                    }
                }

                //ABBA型
                left = i;
                right = i + 1;
                while (true)
                {
                    if (left >= 0 && right < length && chars[left] == chars[right])
                    {
                        if (right - left + 1 > maxCount)
                        {
                            maxCount = right - left + 1;
                        }
                        //继续扩散，尝试取得最大长度
                        left--;
                        right++;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            return maxCount;
        }

        /// <summary>
        /// 动态规划法
        /// </summary>
        static int GetPalindromeMaxCount02(string str)
        {
            if (string.IsNullOrEmpty(str))
            {
                return 0;
            }
            var chars = str.ToCharArray();
            int maxCount = 0;
            int length = chars.Length;

            bool[,] dp = new bool[length, length];

            for (int i = 0; i < length; i++)
            {
                for (int j = 0; j <= i; j++)
                {
                    //此时指向同一个字符
                    if (i - j == 0)
                    {
                        //dp[j, i] = true表示j-i个字符形成的回文串
                        dp[j, i] = true;
                    }
                    else if (i - j == 1 && chars[j] == chars[i])
                    {
                        dp[j, i] = true;
                    }
                    else
                    {
                        // 状态转移：如果左右两字符相等,并且[j+1...i-1]范围内的字符是回文子串
                        // 则 [j j+1...i-1 i] 即[j...i] 也是回文子串
                        if (chars[j] == chars[i] && dp[j + 1, i - 1])
                        {
                            dp[j, i] = true;
                        }
                    }

                    //更新最大长度
                    if (dp[j, i] && i - j + 1 > maxCount)
                    {
                        maxCount = i - j + 1;
                    }
                }
            }



            return maxCount;
        }
    }
}