L2-008 最长对称子串 (25 分)
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定 Is PAT&TAP symmetric?
,最长对称子串为 s PAT&TAP s
,于是你应该输出 \(11\)。
输入格式:
输入在一行中给出长度不超过 \(1000\) 的非空字符串。
输出格式:
在一行中输出最长对称子串的长度。
输入样例:
Is PAT&TAP symmetric?
输出样例:
11
参考代码:
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
int pos[maxn<<1];
string s,t;
inline int pre()
{
t="$#";
for(int i=0;s[i]!='\0';i++)
{
t+=s[i];
t+='#';
}
return 2*s.length()+2;
}
inline int Manacher()
{
int len=pre(),mid=1,r=0,ans=1;
for(int i=1;i<len;i++)
{
if(i<r)pos[i]=min(r-i,pos[mid*2-i]);
else pos[i]=1;
while(t[i-pos[i]]==t[i+pos[i]])pos[i]++;
if(r<i+pos[i])
{
mid=i;
r=i+pos[i];
}
ans=max(ans,pos[i]-1);
}
return ans;
}
int main()
{
getline(cin,s);
cout<<Manacher()<<endl;
return 0;
}
原文链接: https://www.cnblogs.com/LengYun/p/14691149.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/352261
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!