LeetCode5. Longest Palindromic Substring(中心拡散法)

一、問題の説明
Given a string s,find the longest palindromic substring(最長回文文字列)in s.You may assume that the maximum length of s 1000.
Example:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example:
Input: “cbbd”
Output: “bb”
二、考え方(中心拡散法Spread From Center)

forで文字列の各文字をループし、1文字を見つけるたびにこれを中心に左右の文字列が等しいかどうかを両側に広げます.

しかし、回文には奇数と偶数の2種類があり、以下のように奇数回文:aba偶数回文:abbaなので処理する際には、この2つの状況を考慮する必要があります.

アルゴリズムは理解が簡単で、肝心なのは構想です.

アルゴリズム時間効率O(n^2)

三、プログラム例
C#バージョン

class Program
{
    //     
    public static string LongestPalindrome(string s)
    {
        if (s.Length<2)
        {
            return s;
        }

        int start = 0;
        int end = 0;
        int maxLen = 0;

        for (int i = 0; i < s.Length; i++)
        {
            //  bab  
            int m = i;
            int n = i;
            while (((m-1)>=0) && (n+1if (s[m-1] == s[n+1])
                {
                    m--;
                    n++;
                }
                else
                {
                    break;
                }
            }

            if (maxLen < n-m+1)
            {
                start = m;
                end = n;
                maxLen = n - m + 1;
            }

            //  baab  
            m = i;
            n = i+1;
            while (m>=0 && nif (s[m]==s[n])
                {
                    m--;
                    n++;
                }
                else
                {
                    break;
                }
            }

            if (m!=i && maxLen < (n - 1 -(m+1) + 1))
            {
                start = m + 1;
                end = n - 1;
                maxLen = end - start + 1;
            }
        }

        return s.Substring(start, maxLen);
    }

    static void Main(string[] args)
    {
        //string str = "abaaba";
        //string str = "eabcb";
        string str = "ccc";
        //string str = "cbbd";
        string result = LongestPalindrome(str);
    }
}

END.