hihoCoder#1032 : 最长回文子串

方法一：暴力法

枚举所有子串进行判断，复杂度O(n^3)，实现略过（这么写，面试应该会挂）

方法二：动态规划（TLE）

P[i,j] =P[i+1,j-1], if(s[i]==s[j])
P[i,j] =0 ,if(s[i]!=s[j])

#include <iostream>
using namespace std;

int dpstr(string s)
{
    int result = 1;
    int n = s.size();
    bool** plen = new bool*[n];
    for(int i = 0; i <n; i++)
        plen[i] = new bool[n];
    for(int i = 0; i < n; i++)
    {
        plen[i][i] = 1;
        if(i != n - 1)
        {
            if(s[i + 1] == s[i])
            {
                plen[i][i + 1] = true;
                result = 2;
            }
            else
                plen[i][i + 1] = false;
        }
    }
    for(int j = 1; j < n; j++)
    {
        for(int i = 0; i < j; i++)
        {
            plen[i][j] = s[i] == s[j] ? plen[i + 1][j - 1]: false;
            if(plen[i][j])
                result = max(result, j - i + 1);
        }
    }

    for(int i = 0; i <n; i++)
        delete []plen[i];
    delete []plen;
    return result;
}

int main()
{
    int n;
    cin >> n;
    string s;
    while(n--)
    {
        cin >> s;
        cout << dpstr(s) << endl;
    }
    return 0;
}

方法三：扩展字符串（AC）

对每个中心扩展求最长子串，但是这里有个巧妙的地方，中心不是单纯只某个字符，而是把一连串相同的字符都作为一个中心，对于相同字符多的字符串，能够明显提高效率。

#include <iostream>
using namespace std;

int externstr(string a) {
    int result = 0;
    int length = a.size();
    for(int i = 0; i < length; i++) {
        int s = i;
        int e = i;
        while(e + 1 < length && a[e + 1] == a[s]) e++; //先解决相同字符问题
        i = e; //相同字符的中心可以跳过，因为都一样
        while(e + 1 < length && s >= 1 && a[e + 1] == a[s - 1]) {
            e++;
            s--;
        }
        result = max(result, e - s + 1);
    }
    return result;
}

int main()
{
    int n;
    cin >> n;
    string s;
    while(n--) {
        cin >> s;
        cout << externstr(s) << endl;
    }
    return 0;
}

方法四：Manacher法（AC）

Manacher法是目前比较快速的方法，复杂度为O(n)。之前见过好几次也没仔细看过，今天仔细看了下，觉得真的巧妙啊。
主要参考文章：http://blog.sina.com.cn/s/blog_70811e1a01014esn.html

rad[i]-k<rad[i-k]

因为rad[i]-k（橙色）<rad[i-k]（绿色），可以得出橙色部分也是回文的，所以rad[i+k]=rad[i]-k，因为如果比这个再大，则黑色范围也相应应该扩大。

rad[i]-k>rad[i-k]

比较容易看出来绿色部分也是rad[i+k]的值，即rad[i-k]，因为如果再大，r[i-k]也应该扩大。

rad[i]-k==rad[i-k]

如果相等比较费事了，因为rad[i+k]至少是绿的部分那么大，但是如果是橙色部分那么大，也是完全有可能的，所以只能把i放到i+k位置，继续计算。

#include <iostream>
using namespace std;

int Manacher(string s)
{
    int newlength = 2 * s.size() + 1;
    int* rad = new int[newlength]; //回文串半径
    string newstr = ""; //把字符串扩展成字母间和开头结尾都有#的字符串
    for(int i = 0; i < s.size(); i++)
    {
        newstr += '#';
        newstr += s[i]; 
    }
    newstr += '#';

    int nowrad = 0;
    int result = 0;
    for(int i = 0; i < newlength;)
    {
        while(i - nowrad - 1 >= 0
                && i + nowrad + 1 < newlength
                && newstr[i - nowrad - 1] == newstr[i + nowrad + 1])
            nowrad++;
        rad[i] = nowrad;
        result = max(result, rad[i]);

        int k = 1;
        //根据rad[i]-k 和 rad[i-k]的大小进行操作，如果相等的话无法判断准确数值，所以从i+k处继续
        for(; k <= rad[i] && rad[i] - k != rad[i - k]; k++) {
            rad[i + k] = min(rad[i] - k, rad[i - k]);
            result = max(result, rad[i + k]);
        }

        if(k <= i)
            nowrad = rad[i - k];
        else
            nowrad = 0;

        i += k;
    }

    delete []rad;
    return result; //扩展之后的最长子串，肯定是#开头和结尾，所以最长长度就是半径长度
}

int main()
{
    int N;
    string s;

    cin >> N;
    while(N--)
    {
        cin >> s;
        int result = Manacher(s);
        cout << result <<endl;
    }
    return 0;
}