kbs超级中国第五集,小孩脾气暴躁,折纸飞机
看到回文串，自然就会想到
。
还要求子串长度。那就用\(sam\)。
所以每次用manacher找到一个回文串，都在\(sam\)上查询其出现次数。
在\(sam\)上查询的时候，肯定不能暴力找。先找到当前回文串的结束位置。然后用倍增法往上跳。一直跳到长度和当前回文串长度相同。
这个题有点卡空间。卡了很久才卡过去。
我要评论/*
* @author: wxyww
* @date: 2019-07-12 17:23:51
* @last modified time: 2019-07-13 10:11:46
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int lgn = 20,n = 600000 + 100;
// #define int ll
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
char s[n],s[n];
struct node {
int fa,ch[26],len;
}sam[n];
int siz[n],lst = 1,tot = 1,pos[n];
void add(int c,int id) {
int p = lst,cur = ++tot;
sam[cur].len = sam[lst].len + 1;
pos[id] = cur;siz[cur] = 1;
while(p && !sam[p].ch[c]) {
sam[p].ch[c] = cur;
p = sam[p].fa;
}
if(!p) sam[cur].fa = 1;
else {
int q = sam[p].ch[c];
if(sam[q].len == sam[p].len + 1) sam[cur].fa = q;
else {
int clone = ++tot;
sam[clone] = sam[q];
sam[clone].len = sam[p].len + 1;
while(p && sam[p].ch[c] == q) {
sam[p].ch[c] = clone;
p = sam[p].fa;
}
sam[cur].fa = sam[q].fa = clone;
}
}
lst = cur;
}
int p[n];
int n,tong[n],a[n],st[n][lgn + 1];
ll ans;
void check(int l,int r) {
int p = pos[r];
for(int i = lgn;i >= 0;--i) {
if(sam[st[p][i]].len >= r - l + 1)
p = st[p][i];
}
ans = max(ans,1ll * (r - l + 1) * siz[p]);
}
void manacher() {
int id = 0,mx = 0;
for(int i = 1;i <= n;++i) {
if(id + mx > i) p[i] = min(id + mx - i,p[id * 2 - i]);
check((i - p[i] + 1) / 2,(i + p[i]) / 2);
while(i + p[i] + 1 <= n && i - p[i] - 1 >= 1 && s[i + p[i] + 1] == s[i - p[i] - 1]) {
p[i]++;
check((i - p[i] + 1) / 2,(i + p[i]) / 2);
}
if(i + p[i] > id + mx) id = i,mx = p[i];
}
}
int main() {
scanf("%s",s + 1);
int nn = strlen(s + 1);
s[++n] = '#';
for(int i = 1;i <= nn;++i) {
add(s[i] - 'a',i);
s[++n] = s[i];
s[++n] = '#';
}
for(int i = 1;i <= tot;++i) tong[sam[i].len]++;
for(int i = 1;i <= nn;++i) tong[i] += tong[i - 1];
for(int i = 1;i <= tot;++i) a[tong[sam[i].len]--] = i;
for(int i = tot;i >= 1;--i) siz[sam[a[i]].fa] += siz[a[i]];
siz[1] = 0;
for(int i = 1;i <= tot;++i) {
st[a[i]][0] = sam[a[i]].fa;
for(int j = 1;j <= lgn;++j) st[a[i]][j] = st[st[a[i]][j - 1]][j - 1];
}
manacher();
cout<<ans;
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论