1.使用manacher算法进行检测，时间复杂度为O（n）
2.其中需要对字符串进行预处理，头部加上$，然后间隔加上#,如123变为$#1#2#3#
3.需要额外添加变量id，即最长回文的中心，mx，即最长回文的右边界
4.其中当mx>i，我们有定理p[i]>=min(p[j],mx-i)，其中j为i关于id的对称点，即j=2*id-i；即直接从p[i]进行检测
5.当mx<i时，无法进行更多的预测，需要从p[i]=1开始检测
6.检测完以当前字符串为中心的回文后，如果p[i]+i大于最长回文的右边界，则进行更新mx=p[i]=i,id=i;
描述
小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。
这一天，他们遇到了一连串的字符串，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能分别在这些字符串中找到它们每一个的最长回文子串呢？”
小Ho奇怪的问道：“什么叫做最长回文子串呢？”
小Hi回答道：“一个字符串中连续的一段就是这个字符串的子串，而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串，所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~”
小Ho道：“原来如此！那么我该怎么得到这些字符串呢？我又应该怎么告诉你我所计算出的最长回文子串呢？
小Hi笑着说道：“这个很容易啦，你只需要写一个程序，先从标准输入读取一个整数N（N<=30)，代表我给你的字符串的个数，然后接下来的就是我要给你的那N个字符串（字符串长度<=10^6)啦。而你要告诉我你的答案的话，只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了！你看这就是一个例子。”
- 样例输入
-
3 abababa aaaabaa acacdas
- 样例输出
-
7 5 3
AC代码：
[c language=”++”]
/*
题目：
1.使用manacher算法进行检测，时间复杂度为O（n）
2.其中需要对字符串进行预处理，头部加上$，然后间隔加上#,如123变为$#1#2#3#
3.需要额外添加变量id，即最长回文的中心，mx，即最长回文的右边界
4.其中当mx>i，我们有定理p[i]>=min(p[j],mx-i)，其中j为i关于id的对称点，即j=2*id-i；即直接从p[i]进行检测
5.当mx<i时，无法进行更多的预测，需要从p[i]=1开始检测
6.检测完以当前字符串为中心的回文后，如果p[i]+i大于最长回文的右边界，则进行更新mx=p[i]=i,id=i;
*/
#include<string>
#include <iomanip>
#include<fstream>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
int manacher(string str)
{
vector<int > p(str.size(), 0);
int id = 1;//初始化开始检测回文的中心为1
int mx = 0;//初始化最大的边界值为0
for (int i = 1; i < str.size(); i++)
{
//如果边界值mx大于i，那么p[i] = min(p[2 * id – i], mx – i);
if (mx > i)
p[i] = min(p[2 * id – i], mx – i);
//否则，无法对p[i]进行预测，令p[i]=1
else
p[i] = 1;
//检测回文
while (str[i + p[i]] == str[i – p[i]])
p[i]++;
//如果大于最大边界，则进行更新
if (p[i] + i > mx)
{
mx = p[i] + i;
id = i;
}
}
int maxP=INT_MIN;
for (int i = 0; i < p.size(); i++)
maxP = max(p[i], maxP);
return maxP – 1;
}
/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
int n;
scanf("%d", &n);
while (n–)
{
string str;
cin >> str;
string newStr = "$#";
for (int i = 0; i < str.size(); i++)
{
newStr += str[i] ;
newStr += ‘#’;
}
cout << manacher(newStr) << endl;
}
return 0;
}
[/c]