Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

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

Error message here!

返回登录

Close

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

月殇丶 2019-09-11 19:28:00 阅读数:9 评论数: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