#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string Manacher(string &s)//预处理偶数回文。比如讲abba处理成#a#b#b#a#,这样就形成以#为对称轴的回文串
{
string manachers("#");
for (int i = 0; i < s.length();i++)
{
manachers.push_back(s[i]);
manachers.push_back('#');
}
cout << manachers << endl;
return manachers;
}
int MaxLcpLen(string str)
{
string s = str;
if (str.length() == 0)return 0;
if (str.length() % 2 == 0)
s = Manacher(str);//偶数回文转换成奇数回文，不影响结果
int *pArr = new int[s.length()];//保存每个字符的回文半径
int pR = -1;//之前遍历的字符的最大回文半径最右端的下一个字符
int index = -1;
for (int i = 0; i < s.length();++i)
{
pArr[i] = pR > i ? min(pArr[2*index - i], pR - i) :1;
while (i + pArr[i] < s.length() && i - pArr[i] > -1){
if (s[i + pArr[i]] == s[i - pArr[i]])
pArr[i]++;
else
break;
}
if (i + pArr[i] > pR){
index = i;
pR = i + pArr[i];
}
}
return *max_element(pArr, pArr + s.length());
}
void main()
{
string s = "abc1234321ab";
cout << MaxLcpLen(s)- 1 << endl;
cin.get();
}
