首页 > 代码库 > 【HDU】3068 最长回文
【HDU】3068 最长回文
【算法】manacher
【题解】【算法】字符串
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=300010; int n,p[maxn]; char s[maxn],ss[maxn]; void manacher() { int mx=0,id=0; int ans=0; for(int i=2;i<=n;i++)//$不管 { if(i<mx) { p[i]=min(p[id*2-i],mx-i+1); } else p[i]=1; while(s[i+p[i]]==s[i-p[i]])p[i]++; if(i+p[i]-1>mx) { mx=i+p[i]-1; id=i; } ans=max(ans,p[i]-1); } printf("%d\n",ans); } int main() { while(scanf("%s",ss+1)==1) { int tot=strlen(ss+1); n=2;s[1]=‘$‘;s[2]=‘#‘; for(int i=1;i<=tot;i++)s[++n]=ss[i],s[++n]=‘#‘; manacher(); } return 0; }
【HDU】3068 最长回文
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。