LeetCode5. Longest Palindromic Substring(马拉车算法 Manacher Algorithm)，

LeetCode5. Longest Palindromic Substring(马拉车算法 Manacher Algorithm)，

一、问题描述

Given a string s, find the longest palindromic substring *（最长回文字符串）*in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.

Example:

Input: “cbbd”

Output: “bb”

---

二、思路（关键点）

---

三、程序示例

C#版本

class Program
{
     public static string preProcess(string s)
     {
         StringBuilder sb = new StringBuilder();
         sb.Append("$");
         for (int i = 0; i < s.Length; i++)
         {
             sb.Append("#");
             sb.Append(s[i]);
         }

         sb.Append("#");
         //sb.Append("$");

         return sb.ToString();
     }

     public static string LongestPalindrome(string s)
     {
         if (s==null || s.Length==0)
         {
             return null;
         }

         string str = preProcess(s);
         //当前能够向右延伸的最远的回文串中心点，随迭代而更新
         int idx = 0;

         //当前最长回文串在总字符串所能延伸到的最右端的位置
         int max = 0;

         //当前已知的最长回文串中心点
         int maxIdx = 0;

         //当前已知的最长回文串向左或向右能延伸的长度
         int maxSpan = 0;

         int[] p = new int[str.Length];

         for (int curr = 1; curr < str.Length; curr++)
         {
             //找出当前下标相对于idx的对称点
             int symmetryofCur = 2 * idx - curr;
             // 如果当前已知延伸的最右端大于当前下标，我们可以用对称点的P值，否则记为1等待检查
             p[curr] = (max > curr) ? Math.Min(p[symmetryofCur], max - curr) : 1;
             // 检查并更新当前下标为中心的回文串最远延伸的长度
             while ((curr + p[curr])<str.Length && (str[curr + p[curr]] == str[curr - p[curr]]))
             {
                 p[curr]++;
             }
             // 检查并更新当前已知能够延伸最远的回文串信息
             if ((curr + p[curr]) > max)
             {
                 max = p[curr] + curr;
                 idx = curr;
             }

             // 检查并更新当前已知的最长回文串信息
             if (p[curr]>maxSpan)
             {
                 maxSpan = p[curr];
                 maxIdx = curr;
             }
         }

         return s.Substring((maxIdx - maxSpan) / 2, (maxIdx + maxSpan - 1) / 2 - 1 - (maxIdx - maxSpan) / 2 +1 );
     }


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

END.