HDU - 3068 最长回文 (Manacher算法)

HDU - 3068 最长回文

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1010;
int Manacher(string s)
{
    if(s.size() <= 1) return 1;string str = "@#";//一定注意这个@，非常关键，因为在从下标为1的#字符开始求解p数组时没有这个符号就越界了for(int i = 0;i < s.size();i++) {
    str += s[i];str += '#';}vector<int> p(str.size(),0);int mx = 0, id = 0,start = 0,maxlen = 0; for (int i = 1; str[i] != '\0'; i++) {
    //这里如果i在右边界mx之外就只能自己老实匹配了，如果在mx之内需要看p[j]是否大于对称的mx左边界，大于的话说明i位置//的p[i]至少也能延展到以id为中心的回文边界，否则只能是p[j]的值p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;while (str[i + p[i]] == str[i - p[i]]) p[i]++;if (i + p[i] > mx) {
    mx = i + p[i];id = i;}if(p[i]-1 > maxlen){
    start = (i-p[i])/2;//i+p[i]是右边界，所以i-p[i]就是左边界，除以2是因为str加了#变成了两倍长度，所以//在原串的开始位置就是除以2maxlen = p[i]-1;}}return s.substr(start,maxlen).size();
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string str;while(cin>>str){
    cout<<Manacher(str)<<endl;}return 0;
}