Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

马拉车——最长回文子串长度、回文串个数

月殇丶 2019-09-11 19:28:00 阅读数:36 评论数:0 点赞数:0 收藏数:0

题目链接

模板

 #include<bits/stdc++.h>
using namespace std;
 const int maxn=3e5+;

char s[maxn],str[maxn];
 int l1,l2,p[maxn],ans;

void init()
 {
 str[]='$';
 str[]='#';
 for(int i=;i<l1;i++)
  {
 str[i*+]=s[i];
 str[i*+]='#';
  }
 l2=l1*+;
 str[l2]='*';
 }
 int manacher()
 {
 int id=,mx=,ans=;
 for(int i=;i<l2;i++)
  {
 if(mx>i)p[i]=min(p[*id-i],mx-i);
 else p[i]=;
 for(;str[i+p[i]]==str[i-p[i]];p[i]++);
 if(p[i]+i>mx)
  {
 mx=p[i]+i;
 id=i;
  }
 ans=max(ans,p[i]-);
 //ans+=p[i]/2; 回文串个数
 }
 return ans;
 }
 int main()
 {
 while(~scanf("%s",s))
  {
 l1=strlen(s);
  init();
 printf("%d\n",manacher());
  }
 return ;
 }
View Code

 

版权声明
本文为[月殇丶]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/j666/p/11508211.html