题解 | #最长回文子串#

/*
马拉车算法（Manacher's Algorithm）
 
1. 特殊字符0x01，将字符串变为奇数字符串
abba -->  0x01 a 0x01 b 0x01 b 0x01 a 0x01
 
2. 字符串从左到右依次计算回文半径，以 text = "
 0x01 a 0x01 b 0x01 c 0x01 d 0x01 E 0x01 d 0x01 c 0x01 b 0x01 a 0x01 F 0x01 a 0x01 b 0x01 c 0x01 d 0x01 E 0x01 d 0x01 c 0x01 K 0x01 F 0x01
 "
为例。
 
int index = 1;  // 字符串索引
size =  text.size();    // 字符串长度
int radius[size]; // 回文半径长度
数组初始化为1
上面的字符串中:
text[0] = 0x01; 他左边没字符，所以回文就是 他自己 radius[0] = 1
text[1] = 'a'; 他左边0x01，再向左边走，没有字符了\ 他右边边0x01，因为左边只有一个字符，你再去右边找，已经没意义了。
所以他的回文半径就是 他自己+0x01,值为2 -->radius[1] = 2.
 
依次类推
 
text[9] = 'E';左边0x01，右边0x01==>radius[9]++ / 再左边'd' 再右边'd'==>radius[9]++ ,一直循环计算，直到左边不等于右边为止。
得出
radius[9] = 10；
0x01 a 0x01 b 0x01 c 0x01 d 0x01 E 0x01 d 0x01 c 0x01 b 0x01 a 0x01 F 0x01 a 0x01 b 0x01 c 0x01 d 0x01 E 0x01 d 0x01 c 0x01 K 0x01 F 0x01
 
3.
在for 循环中，已经知道'F'的最大回文为10，他的回文半径到 K字符之前的 0x01 字符，设回文半径为RF
1. 当 index 扫描到 F右侧的 字符E 的时候，根据对称性原理，E 的 下标为 index, 那么radius[index] 就要在 (RF - index) 与 对面E对应的半径里面 取得最小值。
这里面 有 为什么要取 两者的最小值，
1.1 当 左侧 E 的 回文半径 RE > RF，我们只知道右侧 E 到 [K字符之前的 0x01 字符] 的半径值，RF以外的，我们不知道，所以此时 radius[index] = RF - index；
1.2 当 左侧 E 的 回文半径 RE < RF，说明 右侧 E 的回文数肯定在 [K字符之前的 0x01 字符] 内区间，所以此时的回文值 radius[index] = radius[IF -(index - IF)] = radius[IF -index + IF]
 
2. 剩余的数据，朴素计算    while 循环
 
*/
#include <iostream>
#include <algorithm>
using namespace std;
 
 
// 转换字符串
void change_text(string& x)
{
    string temp;
    temp.push_back(1);
    temp.push_back(2);  
     
    for(auto v:x)
    {
       temp.push_back(1);
       temp.push_back(v);      
    }
     
    temp.push_back(1);
     
    x = temp;
}
 
 
 
 
int main()
{
    string text;
     
    while(cin >> text)
    {
        if(text.length() == 0)
        {
            cout << 0 << endl;
            continue;
        }
        change_text(text);
        const size_t radius_szie = text.size();
        int radius[radius_szie];
 //       for(int i = 0; i < radius_szie;i++)
  //      {
 //           radius[i] = 1;
 //       }
         radius[0] = 1;
          radius[1] = 1;
          radius[2] = 1;
         
        int Right= 0;// 最右侧位置，即当前已扫描到的最大索引
        int p0 = 0;
        int k = 0;
        int max_Palindrome = 0;
        for(int index = 2; index < radius_szie; index++)
        {
            if(index < Right)
            {
                radius[index] = min(radius[p0 -index + p0], Right-index);
            }
            else
            {
               radius[index] = 1;
            }
            
            // 超出范围之后，再利用中心扩展法 朴素查找
            if (radius[index] >= Right-index)
            {
                // 朴素查找回文 radius[index] 在变化
                while(text[index-radius[index]] == text[index+radius[index]])
                {
                    radius[index]++;
                }  
            }
 
             
            // 更新最右边界及中心点
            if(Right <  index + radius[index])
            {
                Right = index + radius[index];
                p0 = index;
            }
             
            // 最长回文长度计算，因为里面已经插了特殊字符，所以不用除以2
            if(max_Palindrome < radius[index]-1)
            {
                max_Palindrome = radius[index]-1;
            }
             
        }
         
        cout << max_Palindrome << endl;
         
    }
     
     
     
    return 0;
}