题目的主要信息：

• 给定一个仅包含小写字母的字符串，求它的最长回文子串的长度
• 回文串，指左右对称的字符串
• 进阶：时间复杂度$O(n)O(n)$，空间复杂度：$O(n)O(n)$

方法一：暴力法

具体做法：

可以暴力遍历字符串每个字符作为起点，然后遍历每个起点所有长度的子串，检查该子串是否是回文子串。检查的时候，我们可以从子串首尾开始往中间靠，比较首尾，如果都相同就是回文，否则不是回文。我们每次检查完是回文子串，就更新维护最大长度即可。

#include<iostream>
#include<string>
using namespace std;

bool check(string& s, int begin, int end){ //检查子串是否是回文字符串
    while(begin <= end){ //首尾双指针比较
        if(s[begin++] != s[end--])
            return false;
    }
    return true;
}

int main(){
    string s;
    while(cin >> s){
        int maxlen = 1;
        for(int i = 0; i < s.length(); i++){ //遍历每一个字符串作为起点
            for(int j = 0; i + j < s.length(); j++){ //遍历每个起点的每个长度的子串
                if(check(s, i, i + j)) //检查子串是否是回文
                    maxlen = max(maxlen, j + 1); //更新最大值
            }
        }
        cout << maxlen << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n^3)O(n^3)$，遍历所有的子串需要$O(n^2)O(n^2)$，检查每个子串是否是回文需要$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：中心扩展法

具体做法：

也可以遍历每个字符，以该字符为中心（分奇数长度和偶数长度两种情况），不断向两边扩展，如果两边都是相同的就是回文，不断扩大到最大长度即是以这个字符为中心的最长回文子串，我们比较完每个字符为中心的最长回文子串，取最大值即可。

#include<iostream>
#include<string>
using namespace std;

int fun(string& s, int begin, int end){
    while(begin >= 0 && end < s.length() && s[begin] == s[end]){ //每个中心点开始扩展
        begin--;
        end++;
    }
    return end - begin - 1; //返回长度
} 
int main(){
    string s;
    while(cin >> s){
        int maxlen = 1;
        for(int i = 0; i < s.length() - 1; i++) //以每个点为中心
            maxlen = max(maxlen, max(fun(s, i, i), fun(s, i, i + 1))); //分奇数长度和偶数长度向两边扩展
        cout << maxlen << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，遍历字符串每个字符，每个字符的扩展都要$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，无额外空间

方法三：manacher算法

具体做法：

方法二讨论了两种情况，子串长度为奇数和偶数的情况，但其实我们可以对字符串添加不属于里面的特殊字符，来让所有的回文串都变成奇数形式。

同时上述中心扩展法有很多重复计算，manacher就可以优化：我们用maxpos表示目前已知的最长回文子串的最右一位的后一位，用index表示当前的最长回文子串的中心点。对于给定的 i 我们找一个和它关于index对称的 j ，也就是$index-j==i-indexindex-j\; ==\; i-index$，换言之就是$j==2\ast index-ij==2*index-i$。

如果发生这种情况,我们就不难发现, i 和 j 的最长回文子串在index的回文串范围内的部分应该是一模一样的，但是在外面的部分就无法保证了,当然,最好的情况是i和j的回文子串范围都很小,这样就保证了它们的回文子串一定一模一样,对于超出的部分我们也没有办法, 只能手动使用中心扩展。

最后答案计算的时候需要考虑使用预处理，长度被加了一倍，于是结果是 max(mp[i]-1)。

#include<iostream>
#include<string>
#include<vector>
using namespace std;

void manacher(string& s, int n, vector<int>& mp){
    string ms = "";
    ms += "$#";
    for(int i = 0; i < n; i++){ //预处理
        ms += s[i]; //使之都变成奇数回文子串
        ms += '#';
    }
    int maxpos = 0; // 目前已知的最长回文子串的最右一位的后一位
    int index = 0; // 当前的最长回文子串的中心点
    for(int i = 0; i < ms.length(); i++){ 
        mp[i] = maxpos > i ? min(mp[2 * index - i], maxpos - i) : 1; 
        while(ms[i + mp[i]] == ms[i - mp[i]]) //两边扫
            mp[i]++;
        if(i + mp[i] > maxpos){ //更新位置
            maxpos = i + mp[i];
            index = i;
        }
    }
}

int main(){
    string s;
    while(cin >> s){
        int n = s.length();
        vector<int> mp(2 * n + 2); //记录回文子串长度
        manacher(s, n, mp);
        int maxlen = 0;
        for(int i = 0; i < 2 * n + 2; i++) //遍历数组
            maxlen = max(maxlen, mp[i] - 1);  //找到最大的长度
        cout << maxlen << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，都是单层遍历，函数中的while循环累计也不会超过$2n2n$次
• 空间复杂度：$O(n)O(n)$，长度为$2\ast n2*n$的预处理后的字符串和长度为$2\ast n+22*n+2$的数组