AcWing 3188. manacher算法
原题链接
中等
作者:
灵茶气艾福
,
2021-08-27 12:29:31
,
所有人可见
,
阅读 341
C++ 代码
#include <bits/stdc++.h>
#include <string.h>
#include <map>
#include <stack>
using namespace std;
const int maxn=1e7+10;
char temp[maxn*2];
int P,po,q[maxn*2];
string str;
int res=1;
int init(string s){ //返回转换后的字符串的长度
int len=s.length();
temp[0]='$';
for(int i=1;i<len*2+1;i+=2){
temp[i]='#';
temp[i+1]=s[i/2];
}
temp[len*2+1]='#';
temp[len*2+2]='^';
return len*2+1;
}
int main(){
getline(cin,str);
int len=init(str);
for(int i=1;i<=len;i++){
if(P>i) q[i]=min(P-i,q[po*2-i]);
else q[i]=1;
while(temp[i-q[i]]==temp[i+q[i]]){
q[i]++;
}
if(q[i]+i>P) {
P=q[i]+i;
po=i;
}
res=max(q[i],res);
}
cout<<res-1<<endl;
system("pause");
return 0;
}