首页 > 代码库 > 【51NOD-0】1089 最长回文子串 V2(Manacher算法)
【51NOD-0】1089 最长回文子串 V2(Manacher算法)
【算法】回文树
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=100010; struct trees{int len,fail,t[260];}t[maxn]; char s[maxn]; int n,len,l,sz,ans; int getfail(int x) { while(s[len-t[x].len-1]!=s[len])x=t[x].fail; return x; } void tree_work() { int x=s[++len]; l=getfail(l); if(!t[l].t[x]) { sz++; t[sz].len=t[l].len+2; if(t[sz].len>ans)ans=t[sz].len; t[sz].fail=t[getfail(t[l].fail)].t[x];//偏小 t[l].t[x]=sz; } l=t[l].t[x]; } int main() { scanf("%s",s+1); n=strlen(s+1); sz=1; s[0]=-1;// t[0].len=0;t[1].len=-1; t[0].fail=t[1].fail=1; len=l=ans=0; for(int i=1;i<=n;i++)tree_work(); printf("%d",ans); return 0; }
【51NOD-0】1089 最长回文子串 V2(Manacher算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。