题解 | #最长回文子串#

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

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    public int getLongestPalindrome (string A) {
        A = PreProcess(A);
        //Console.WriteLine(A);
        int l = 0, r = -1;
        int[] dp = new int[A.Length];
        for(int i = 0; i < A.Length; i++){
            //循环更新l，r。并计算dp[i](第i个字符为中心的最长字符串长度)
            if(i >= r){
                int m = 1;
                while((i + m) < A.Length && (i - m) >= 0 && A[i + m] == A[i - m]){
                    m++;
                }
                m--;
                r = i + m;
                l = i - m;
                dp[i] = m;
            }
            else{
                if(dp[r + l - i] < r - i){
                    dp[i] = dp[r + l - i];
                }
                else{
                    int m = r - i + 1;
                    while((i + m) < A.Length && (i - m) >= 0 && A[i + m] == A[i - m]){
                        m++;
                    }
                    m--;
                    r = i + m;
                    l = i - m;
                    dp[i] = m;
                }
            }
        }

        return dp.Max();
    }

    public string PreProcess(string A){
        string newA =  "";
        foreach(char c in A){
            newA += "#" + c;
        }
        newA += "#";
        return newA;
    }
}