Ckger @ 2021-07-26 18:19:36
manacher做法，自己找不出问题了，求助
#include<bits/stdc++.h>
#define foir(i,l,r) for (register int i=l;i<=r;++i)
#define fopr(i,l,r) for (register int i=l;i>=r;--i)
#define maxn 5000010
using namespace std;
int n;
char s[maxn<<1];
int p[maxn<<1];
int mid,r;
int ans;
inline void init()
{
cin>>n;
foir(i,1,n)
{
cin>>s[i*2-1];
s[i*2]='#';
}
s[0]='#';
n=n*2-1;
}
int main()
{
init();
foir(i,1,n)
{
if (i<=r) p[i]=min(r-i+1,p[mid*2-i]);
while (i-p[i]>=0&&i+p[i]<=n+1&&s[i-p[i]]==s[i+p[i]]) ++p[i];--p[i];
if (i+p[i]>r)
{
if (i%2==0)
for (register int j=2;j<=(p[i]+4)/2;j+=2)
if (p[i-j]==j)
ans=max(ans,j*2);
mid=i,r=i+p[i];
}
}
cout<<ans<<endl;
return 0;
}by sssom @ 2021-07-26 19:43:17
提供一个可能比较好想的 manacher：
我们枚举双倍回文串右边部分的中心点时，需要找到这个中心点对应的双倍回文串的中心点。根据双倍回文串的性质，这两个点都应该是特殊符号而不是字母（满足长度为 4 的倍数），并且这两个点应该满足 mid + \frac{p{mid} - 1}{2} \ge imid+ 2 p mid −1 ≥i，其中 midmid 是双倍回文串的中心点，p{mid}p mid 是 midmid 对应的回文串长度 +1，ii 是双倍回文串右边部分的中心点。因为如果 mid + \frac{p_{mid} - 1}{2} < imid+ 2 p mid −1 <i，可以证明此时回文串长度还应该更长，不符合题意。然后我们查找满足这个条件的尽量靠左的 midmid 点就可以了，此时答案就是 2 \times (i - mid)2×(i−mid)，然后我们对这些值取最大值。
为了动态插入、查找符合条件的 midmid 点，我们需要两个 set，第一个 set 里存储按 mid + \frac{p{mid} - 1}{2}mid+ 2 p mid −1 排序元素，第二个 set 存储按 midmid 大小排序的元素。我们每次在第一个 set 里删除对于当前 ii 不满足 mid + \frac{p{mid} - 1}{2} \ge imid+ 2 p mid −1 ≥i 的元素，并在第二个 set 里删除对应的 midmid，查找时直接在第二个 set 里用 lower_bound() 函数就可以了。
by sssom @ 2021-07-26 19:43:46
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int N = 1e6 + 20;
int n, ans;
char s[N];
int p[N];
set<pair<int, int> > s1;
set<int> s2;
void manacher(char *s) {
for (int i = 1, r = 0, id = 0; i < n; i++) {
if (i < r) p[i] = min(p[id * 2 - i], r - i);
else p[i] = 1;
while (s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > r) r = i + p[i], id = i;
if (s[i] == '$') {
s1.insert(make_pair(i + (p[i] - 1) / 2, i));
s2.insert(i);
while (s1.begin()->first < i) s2.erase(s1.begin()->second), s1.erase(s1.begin());
int t = *s2.lower_bound(i - p[i]);
ans = max(ans, (i - t) * 2);
}
}
}
int main() {
s[0] = '#';
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = n * 2 + 1; i >= 1; i--)
if (i & 1) s[i] = '$';
else s[i] = s[i >> 1];
s[n * 2 + 2] = '\0';
n = strlen(s);
manacher(s);
printf("%d", ans);
return 0;
}by Ckger @ 2021-07-26 20:08:14
@sssom 谢谢，但是还能请您看看我的代码吗，我很想知道自己错在哪里（调了好久。。。
by Ckger @ 2021-07-26 20:09:02
@sssom 还有为啥我的代码超时了。。
by peiwenjun @ 2021-10-06 22:55:42
@Ckger 感觉你manacher的p数组都没有求对，一直弄不清楚你的下标是从0开始还是从1开始,(到底是n=2n-1还是n=2n？).我已经调不动了，你自己调吧
附上hack数据：(正确答案0)
30
aabbbabaabbababaabbbaaabbabbab
by Ckger @ 2021-10-06 23:27:58
@peiwenjun 啊这，您是怎么找到这么久远的帖子的。。。这题我p数组是对的，只是计算ans的时候出了一点bug，谢谢您
by peiwenjun @ 2021-10-07 09:07:20
@Ckger 调出来了说一句此贴完结好吗。。。还可以用来警示后人
by Ckger @ 2021-10-07 10:00:00
@peiwenjun 对不起，忘了
by Ckger @ 2021-10-07 10:00:54
现在，此帖完结