最長回文子串的概念

回文串是指正序和反序都一樣的字符串，例如：
Str1 = "AbbA"，則Str1的最長回文子串是它本身“AbbA”，最長回文長度為4；
Str2="AABBAb"，則Str2的最長回文子串是“ABBA”，最長回文長度為4。

解決方案

• 暴力破解
  列出所有子串，判斷子串是否為回文串。

• 利用最長公共子串求解
  根據(jù)回文串的概念，可將原串反序得到新串，然后對原串與新串求最長公共子串即可。最長公共子串的算法可參考http://www.itdecent.cn/p/64dfcef92d5f

• 利用Manacher算法
  利用回文串的對稱特性，可將算法的時間復(fù)雜度降為O(n)，代碼如下：

int initManacher(const char* rawStr, char* const newStr)
{
    int len = strlen(rawStr);
    newStr[0] = '$';
    newStr[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++)
    {
        newStr[j++] = rawStr[i];
        newStr[j++] = '#';
    }

    newStr[j] = '\0';
    return j;
}

int manacher(const char* rawStr)
{
    char* newStr = (char*)calloc(strlen(rawStr) * 2 + 3, sizeof(char));
    int* p = (int*)calloc(strlen(rawStr) * 2 + 3, sizeof(int)); // p[i]的值表示以i為中心的最長回文半徑
    int len = initManacher(rawStr, newStr);  // 將字符串的長度轉(zhuǎn)為奇數(shù)并以"$"開始，"\0"結(jié)尾
    int max_len = -1;  // 最長回文長度

    int center = 0;     // center的主要作用是作為回文的中心，這個軸中心是從左往右跳躍著變化的
    int radius = 0;     // 以center為中心的最大回文半徑的下標(biāo)，radius - center為以center為中心的最大回文半徑，也即radius - center == p[center]

    for (int i = 1; i < len; i++)
    {
        if (i < radius)     // 如果i在以center為中心，回文半徑為radius - center的范圍內(nèi)，則可以利用回文的特性，快速求取p[i]的值。 p[2 * center - i]是i以center為中心的對稱點的值
            p[i] = min(p[2 * center - i], radius - i);  // 計算出p[i]的最小可能值
        else                // 如果不在該半徑內(nèi)，則無法利用回文的特性，只能按普通的方法來一步一步求取p[i]的準(zhǔn)確值，最開始的默認值為1
            p[i] = 1;

        // 因為上面計算所得的p[i]值為最小可能值，p[i]的準(zhǔn)確值還需通過不斷擴展來判斷，這個while循環(huán)不斷擴展以i為中心的回文半徑（i當(dāng)前的回文半徑外的第一個位置的值如果兩邊都相等，說明回文半徑還可以加1）。注意，這里不需邊界判斷，因為左有'$',右有'\0'
        while (newStr[i - p[i]] == newStr[i + p[i]])
            p[i]++;

        // 我們每走一步 i，都要和 radius 比較，我們希望 radius 盡可能的遠，這樣才能更有機會執(zhí)行 if (i < radius)這句代碼，從而提高效率
        if (radius < i + p[i])
        {
            center = i;     // 更新center的位置
            radius = i + p[i];  // 更新為以新center為中心的最大回文半徑
        }

        max_len = max(max_len, p[i] - 1);
    }

    free(newStr);
    free(p);
    return max_len;
}