题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3676
离线版题目:http://paste.ubuntu.com/17527319/
数据生成:http://paste.ubuntu.com/17528560/
哎呀,现在是下午5:47,我为了写这道题,现在周末作业只完成了1/3,呵呵呵呵!
来说一说坎坷的历程吧:
1. 10min 确定 SA + manacher
2. 1h 码完代码
3. 6h 调试代码,BZOJ仍然超时QAQ
4. UOJ上发现原题,提交,通过!
讲到这里,我只能说,BZOJ数据好强!
————————————————— 我是华丽丽的分割线,下面才是正文 ———————————————————
解题思路:manacher找出所有本质不同的回文串,sa来查询出现了多少次
被卡原因:SA模板出错,ST表模板出错,manacher的使用还有一点小问题
HINT:
1.网上很多代码都有问题,比如hzwer的就可以被“abbababbbb”卡掉,正解7,hzwer输出8(他的马拉车写错了)
2.BZOJ数据太强,SA + manacher要T,不过UOJ可过(其实在manacher那里分类讨论的话,也是可以卡过的)
3.会用SAM的就不要用SA做死啦(或者你要用DC3应该也是可以过的,但是我不会QAQ)
4.会用回文自动机的就不要用manacher做死啦!
5.刚才都说了网上的代码可能有错,所以能过就好
6.此题必须不放过任意一个本质不同的回文串,否则正确性有问题,哎呀刚才自己出的那组数据找不到了QAQ
7.答案会爆int
Inspiration:对于manacher来说,本质不同的回文串一定是能使右边界指针向右移的串
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 1210000;
char BUF[MAXN],pat[MAXN];
int n,rep[MAXN],LEN[MAXN];
LL vout=1;
inline void init(){
gets(BUF+1);
n = strlen(BUF+1);
for (int i=1;i<=n;i++){
pat[i*2-1] = 123;
pat[i*2] = BUF[i];
} n = n*2+1;
pat[n]=123; LEN[1] = 0;
for (int i=2;i<=n;i++)
LEN[i] = LEN[i>>1]+1;
}
namespace Suffix_Array{
#define SA Suffix_Array
#define SIGMA_SIZE 30
int sa[MAXN],bot[MAXN],t1[MAXN],t2[MAXN],*tmp,*rank;
int m,height[MAXN];
namespace Sparse_Table{
#define ST Sparse_Table
int mx[MAXN][17];
inline void init(){
for (int i=1;i<=n;i++)
mx[i][0] = height[i];
for (int i=1,len=1;len<=n;i++,len*=2){
for (int j=1;j<=n;j++)
mx[j][i] = min(mx[j][i-1],mx[j+len][i-1]);
}
}
inline int query(int l, int r){
int t=LEN[r-l+1];
return min(mx[l][t],mx[r-(1<<t)+1][t]);
}
};
inline void GetHeight(char *s){
for (int i=1,t=0;i<=n;i++){
if (t) t--;
int p1 = i+t, p2 = sa[rank[i]-1]+t;
while (s[p1++] == s[p2++]) t++;
height[rank[i]] = t;
}
pat[n+1]=125; pat[0]=124;
ST::init();
}
inline void build(char *s){
m = SIGMA_SIZE; tmp = t1; rank = t2;
for (int i=1;i<=n;i++) bot[tmp[i]=s[i]-'a'+1]++;
for (int i=2;i<m;i++) bot[i] += bot[i-1];
for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++)
if (s[sa[i]] != s[sa[i-1]]) rank[sa[i]] = ++m;
else rank[sa[i]] = m;
for (int k=1,T=0;k<=n;k*=2,T=0){
for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
for (int i=1;i<=m;i++) bot[i] = 0;
for (int i=1;i<=n;i++) bot[rank[i]]++;
for (int i=2;i<=m;i++) bot[i] += bot[i-1];
for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
swap(tmp,rank);
rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++)
if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]] = m;
else rank[sa[i]] = ++m;
if (m >= n) break;
}
GetHeight(s);
}
inline int match_right(int s,int len){
int l = 1, r = n-s,ret=1;
while (l <= r){
int mid = (l + r) / 2;
if (ST::query(s+1,s+mid) >= len) ret = mid, l=mid+1;
else r = mid-1;
}
return ret;
}
inline int match_left(int s,int len){
int l = 1, r = s,ret=1;
while (l <= r){
int mid = (l + r) / 2;
if (ST::query(s-mid+1,s) >= len) ret = mid, l=mid+1;
else r = mid-1;
}
return ret;
}
inline int search(int s, int len){
int ret = 1, pos = rank[s];
if (height[pos] >= len && pos > 1) ret += match_left(pos,len);
if (height[pos+1] >= len && pos < n) ret += match_right(pos,len);
return ret;
}
};
inline void solve(int i){
int beg = i-rep[i];
int t = SA::search(beg,rep[i]*2+1);
vout = max(vout, (LL)t*(LL)rep[i]);
}
inline void manacher(){
int itr=0;
for (int i=1;i<=n;i++){
if (rep[itr]+itr > i) rep[i] = min(rep[itr*2-i],rep[itr]+itr-i);
else rep[i] = 0;
int p1 = i+rep[i], p2 = i-rep[i];
while (pat[--p2]==pat[++p1])
rep[i]++, solve(i);
if (rep[i]+i > rep[itr]+itr) itr = i;
}
printf("%lldn",vout);
}
int main(){
init();
SA::build(pat);
manacher();
return 0;
}
来补一发后缀自动机,这简直是屠场啊!
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 300000+9;
char pat[MAXN];
namespace Palindromic_Tree{
#define PAM Palindromic_Tree
#define SIGMA_SIZE 26
int ch[MAXN][SIGMA_SIZE],sz[MAXN],fail[MAXN];
int n,cnt,last,len[MAXN];
inline void init(){
cnt = 1;
fail[0] = fail[1] = 1;
len[1] = -1;
}
inline void expend(int pos, int c, char *s){
int cur = last;
while (s[pos-len[cur]-1] != s[pos]) cur = fail[cur];
if (!ch[cur]){
int w = ++cnt, k = fail[cur];
len[w] = len[cur] + 2;
while (s[pos-len[k]-1] != s[pos]) k = fail[k];
fail[w] = ch[k]; ch[cur] = w;
}
last = ch[cur];
sz[last]++;
}
inline void build(char *s){
init();
n = strlen(s+1);
for (int i=1;i<=n;i++)
expend(i,s[i]-'a',s);
}
inline LL solve(){
LL ret = 1;
for (int i=cnt;i;i--){
sz[fail[i]] += sz[i];
ret = max(ret, (LL)len[i]*(LL)sz[i]);
}
return ret;
}
};
int main(){
scanf("%s",pat+1);
PAM::build(pat);
printf("%lldn",PAM::solve());
return 0;
}