链接
https://vjudge.net/problem/UVA-1470
题解
w
w
r
w
w
r
ww^rww^r
wwrwwr这东西看起来十分回文 我想了半天，发现可以这样判断一个子串是否符合条件： 假设
w
w
w的长度为
u
u
u 那么第一个
w
w
w和第一个
w
r
w^r
wr之间的位置肯定是一个对称轴，两边长度为
u
u
u的区域是关于这个轴对称的，也就是说这里有一个长度不低于
u
u
u的回文串 再以第一个
w
r
w^r
wr和第二个
w
w
w的中心为轴，肯定有一个长度不低于
2
u
2u
2u的回文串 令
a
i
a_i
ai表示以
i
i
i和
i
+
1
i+1
i+1的缝隙为对称轴的回文串的长度 那么一个
w
w
r
w
w
r
ww^rww^r
wwrwwr就体现在
a
a
a序列中有两个数
a
j
,
a
j
(
i
<
j
)
a_j,a_j(i<j)
aj,aj(i<j)，满足
a
i
≥
u
a_i\geq u
ai≥u，
a
j
≥
2
u
a_j \geq 2u
aj≥2u，且
j
−
i
=
u
j-i=u
j−i=u 那么现在就是序列问题了 我如果枚举
i
i
i，那么就成了找满足
a
i
≥
j
−
i
a_i \geq j-i
ai≥j−i，
a
j
≥
2
j
−
2
i
a_j \geq 2j-2i
aj≥2j−2i的最大的
j
j
j 化简一下得，
i
≤
j
≤
i
+
a
i
i\leq j \leq i+a_i
i≤j≤i+ai，
2
j
−
a
j
≤
2
i
2j-a_j \leq 2i
2j−aj≤2i 其实就是在
[
i
,
i
+
a
i
]
[i,i+a_i]
[i,i+ai]这个区间去找满足条件
2
j
−
a
j
≤
2
i
2j-a_j\leq 2i
2j−aj≤2i的最大的
j
j
j 因为
2
i
2i
2i单调增加，所以我可以把所有的
j
j
j按照
2
j
−
a
j
2j-a_j
2j−aj排序，用一个指针每次往后移动一下把符合条件的
j
j
j加到树状数组中去，每次查询
[
1
,
i
+
a
i
]
[1,i+a_i]
[1,i+ai]的前缀最小值，如果最小值
x
x
x不小于
i
i
i，那么就用
u
=
x
−
i
u=x-i
u=x−i更新答案
代码
#include <bits/stdc++.h>
#define maxn 600010
#define lowbit(x) ((x)&-(x))
#define cl(x) memset(x,0,sizeof(x))
using namespace std
;
struct Manacher
{
int r
[maxn
], p
[maxn
], n
;
void clear(){cl(r
), cl(p
);}
void calc(int *s
, int N
)
{
n
=N
;
int i
, j
, mx(0), center
;
r
[0]=-2;
for(i
=1;i
<=N
;i
++)r
[2*i
]=s
[i
];
for(i
=1;i
<=N
;i
++)r
[2*i
-1]=-1;
r
[2*N
+1]=-1;
for(i
=1;i
<=2*N
+1;i
++)
{
if(mx
>=i
)p
[i
]=min(p
[2*center
-i
],mx
-i
+1);
else p
[i
]=1;
while(r
[i
-p
[i
]]==r
[i
+p
[i
]])p
[i
]++;
if(i
+p
[i
]-1>mx
)
{
mx
=i
+p
[i
]-1;
center
=i
;
}
}
}
}mnc
;
struct BIT
{
int a
[maxn
], n
;
void clear(){cl(a
);}
void add(int pos
, int v
)
{
for(;pos
<=n
;pos
+=lowbit(pos
))a
[pos
]=max(a
[pos
],v
);
}
int pre_max(int pos
)
{
int ans(0);
for(;pos
;pos
-=lowbit(pos
))ans
=max(ans
,a
[pos
]);
return ans
;
}
}bit
;
char s
[maxn
];
int len
, r
[maxn
], a
[maxn
];
void init()
{
int i
;
scanf("%s",s
+1);
len
=strlen(s
+1);
cl(r
);
for(i
=1;i
<=len
;i
++)r
[i
]=s
[i
];
mnc
.clear();
mnc
.calc(r
,len
);
}
vector
< pair
<int,int> > d
;
void work()
{
int i
, j
, x
, ans(0), p(0);
for(i
=1;i
<=len
;i
++)
a
[i
]=(mnc
.p
[i
*2+1]-1)/2;
d
.clear();
for(j
=1;j
<=len
;j
++)
d
.emplace_back( make_pair(j
-a
[j
]/2,j
) );
sort(d
.begin(),d
.end());
bit
.clear();
bit
.n
=len
;
for(i
=1;i
<=len
;i
++)
{
while(p
<d
.size())
{
if(d
.at(p
).first
<= i
)
{
bit
.add(d
.at(p
).second
,d
.at(p
).second
);
p
++;
}
else break;
}
j
=bit
.pre_max(i
+a
[i
]);
if(j
>=i
)ans
=max(ans
,j
-i
);
}
printf("%d\n",ans
*4);
}
int main()
{
int T
;
scanf("%d",&T
);
while(T
--)
{
init();
work();
}
return 0;
}
