「BZOJ2342」[SHOI2011] 双倍回文
Description
.jpg)
Input
输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。
Output
输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。
Sample Input
16
ggabaabaabaaball
Sample Output
12
HINT
N<=500000
题解
p[i]表示i和i+1为中心的最长回文子串长度/2（str[i-k]=str[i+1+k]）。。。
用manacher On计算p数组
题目要求计算w wR w wR的最大长度
枚举x为对称轴。。。实际上对称轴在x到x+1之间，即x是第一个wR的最后一位
举些例子推一推发现len(x+1,y)*4能更新答案，仅当y-p[y]<=x且y<=x+p[x]/2
按照y-p[y]排序一下，递推x的时候将符合1式的y插入set，在set中查找x+p[x]/2的前驱更新答案即可
复杂度On+nlogn
usedtobe提出如果把题目要求改成w wR w。。。这样的话限制应该是y<=x+p[x]且y-p[y]<=x
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000007 #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; char ch[500005]; int p[500005],q[500005]; set<int> t; void manacher() { int mx=0,id; for(int i=1;i<=n;i++) { if(mx>=i)p[i]=min(mx-i,p[2*id-i]); else p[i]=0; for(;ch[i+p[i]+1]==ch[i-p[i]];p[i]++); if(p[i]+i>mx)id=i,mx=p[i]+i; } } bool cmp(int a,int b) { return (a-p[a])<(b-p[b]); } int main() { n=read(); scanf("%s",ch+1); ch[0]='#'; manacher(); for(int i=1;i<=n;i++)q[i]=i; sort(q+1,q+n+1,cmp); int now=1; for(int i=1;i<=n;i++) { while(now<=n&&q[now]-p[q[now]]<=i) { t.insert(q[now]); now++; } set<int>::iterator tmp=t.upper_bound(i+p[i]/2); if(tmp!=t.begin()) { ans=max(ans,(*--tmp-i)*4); } } printf("%d\n",ans); return 0; } |
Subscribe
计数器 9318412
OI 课件=>
OI 课件=>