首页 > 代码库 > hdu 3068 最长回文子串 马拉车模板
hdu 3068 最长回文子串 马拉车模板
前几天用后缀数组写过一次这题,毫无疑问很感人的TLE了-_-||
今天偶然发现了马拉车模板,O(N)时间就搞定
reference:http://acm.uestc.edu.cn/bbs/read.php?tid=3258
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 #define N 110010 6 char s[N*2],str[N*2]; 7 int n,p[N*2]; 8 9 void fun()10 {11 int len=(int)strlen(s);12 str[0]=‘$‘;str[1]=‘#‘;13 n=2;14 for(int i=0;i<len;i++)15 {16 str[n++]=s[i];17 str[n++]=‘#‘;18 }19 str[n]=‘\0‘;20 }21 22 void Manacher()23 {24 int i,id,mx=0;25 for(i=1;i<n;i++)26 {27 if(mx > i)28 p[i]=min(p[2*id-i],p[id]+id-i);29 else30 p[i]=1;31 for(;str[i+p[i]] == str[i-p[i]];p[i]++)32 ;33 if(p[i]+i > mx)34 {35 mx=p[i]+i;36 id=i;37 }38 }39 }40 41 void work()42 {43 int ans=-1;44 for(int i=1;i<n;i++)45 ans=max(ans,p[i]);46 printf("%d\n",ans-1);47 }48 49 int main()50 {51 while(scanf("%s",s)!=EOF)52 {53 fun();54 Manacher();55 work();56 }57 return 0;58 }
hdu 3068 最长回文子串 马拉车模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。