题解 P3649 【[APIO2014]回文串】
beretty
2018-08-08 23:12:09
这道题好像是一道回文树裸题
~~但是我并不会回文树~~
可以用SA+manacher或SAM+manacher
最近刚学$SAM$,所以用$SAM+manacher$过掉了这道题
首先先对原串建立$SAM$
然后跑$manacher$,一旦有回文串就在SAM上进行查询
查询$S(l , r)$在原串中出现多少次
暴力查询一次的复杂度是$O(n)$
总复杂度$O(n^2)$
显然不能通过此题
所以我们可以考虑用倍增快速查询出$S(l,r)$在原串中出现次数
设$st[i][j]$表示$SAM$上的节点i向上跳$2^j$步能到达哪个节点
如果当前节点的$step >= r - l + 1$就说明要查询的回文串仍然是当前节点的一个后缀
就一直往上跳到不能再跳为止
此时的节点所代表的子串的$right$集合大小就是$S(l,r)$在原串中的出现次数辣
这样的时间复杂度$O(nlogn)$,可以通过此题
上代码↓
```
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
# define LL long long
const int M = 600005 ;
using namespace std ;
char s[M] ;
int n , m ;
LL Ans ;
int Last , cnt ;
int size[M] , son[M][26] , fa[M] , step[M] , c[M] , b[M] ;
int p[M] , r[M] , fir[M] ;
int pos[M] , lg[M] , dep[M] , st[M][20] ;
inline void Insert(int c , int id){
int np = ++cnt , p = Last ; step[np] = step[p] + 1 ;
Last = cnt ; size[np] = 1 ; pos[id] = np ;
while(!son[p][c] && p) son[p][c] = np , p = fa[p] ;
if(!p) fa[np] = 1 ;
else {
int q = son[p][c] ;
if(step[q] == step[p] + 1) fa[np] = q ;
else{
int nq = ++cnt ; step[nq] = step[p] + 1 ;
memcpy(son[nq] , son[q] , sizeof(son[q])) ;
fa[nq] = fa[q] ; fa[q] = fa[np] = nq ;
while(son[p][c] == q) son[p][c] = nq , p = fa[p] ;
}
}
}
inline void Build(){
Last = cnt = 1 ;
for(int i = 1 ; i <= n ; i ++) Insert(s[i] - 'a' , i) ;
for(int i = 1 ; i <= cnt; i ++) c[step[i]] ++ ;
for(int i = 1 ; i <= n ; i ++) c[i] += c[i - 1] ;
for(int i = 1 ; i <= cnt; i ++) b[c[step[i]]--] = i ;
for(int i = cnt , p ; i ; i --) {
p = b[i] ;
size[fa[p]] += size[p] ;
}
for(int i = 1 , p ; i <= cnt ; i ++) {
p = b[i] ;
dep[p] = dep[fa[p]] + 1 ;
st[p][0] = fa[p] ;
for(int j = 1 ; (1<<j) <= dep[p] ; j ++)
st[p][j] = st[st[p][j - 1]][j - 1] ;
}
}
inline void Check(int l , int r){
if(l < 1 || r > n) return ;
int now = pos[r] ;
for(int i = lg[dep[now]] ; i >= 0 ; i --) {
int temp = st[now][i] ;
if(step[temp] >= r - l + 1) now = temp ;
}
Ans = max(Ans , 1LL * size[now] * (r - l + 1)) ;
}
inline void Manacher() {
p[++m] = '@' ;
for(int i = 1 ; i <= n ; i ++) p[++m] = '#' , p[++m] = s[i] , fir[m] = i ;
p[++m] = '#' ; p[++m] = '$' ;
int pos = 0 , mx = 0 ;
for(int i = 1 ; i <= m ; i ++) {
if(i < mx) r[i] = min(mx - i , r[pos * 2 - i]) ;
else r[i] = 1 ;
Check(fir[i - r[i] + 2] , fir[i + r[i] - 2]) ;
while(p[i - r[i]] == p[i + r[i]]) ++r[i] , Check(fir[i - r[i] + 2] , fir[i + r[i] - 2]) ;
if(i + r[i] > mx)
mx = i + r[i] , pos = i ;
}
}
int main(){
scanf("%s",s + 1) ; n = strlen(s + 1) ;
for(int i = 2 ; i <= n ; i ++) lg[i] = lg[i >> 1] + 1 ;
Build() ; Manacher() ;
printf("%lld\n",Ans) ;
return 0 ;
}
```