【题解】loj#2579[SHOI2011]双倍回文

一道PAM思维题…

像我这种只会写板子、莫得脑子的选手注定要挨打啊/kk

题面简述:

给定一个串 $\rm S$,求该串最长的「双倍回文子串」。「双倍回文」指的是这么一种子串:自身回文,且前半部分、后半部分均回文。

$\rm |S|\leq 10^6$

考虑PAM。但发现似乎不是很好做,因为每次转移是像串的两端各加一个字符,有点gg。但是仔细思考就会发现,PAM的 $fail$ 实际指向的是最长的回文后缀,而我们的所求也是这么一个回文后缀的形式,只不过限制了长度。

所以考虑求PAM的时候顺便维护另一个 $fail’$,其意义是「不超过当前串长一半的回文后缀」。

思考原来PAM的构造方式:

1
2
3
4
5
6
7
8
9
10
11
12
void _insert(PAM &p, int x, int pos, char *s){
int u = p.last ;
while (s[pos - p.len[u] - 1] != s[pos]) u = p.fail[u] ;
if (!p.trie[u][x]){
int fa = p.fail[u] ;
int newn = ++ p.sz ;
p.len[newn] = p.len[u] + 2 ;
while (s[pos - p.len[fa] - 1] != s[pos]) fa = p.fail[fa] ;
p.fail[newn] = p.trie[fa][x], p.trie[u][x] = newn ;
}
p.last = p.trie[u][x] ;
}

可以类推出新的构造:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Ins(int x, int pos){
int p = last, q, np, nq ;
while (S[pos] != S[pos - len[p] - 1]) p = fail[p] ;
if (!trans[p][x]){
np = ++ sz, q = fail[p] ;
while (S[pos] != S[pos - len[q] - 1]) q = fail[q] ;
len[np] = len[p] + 2, fail[np] = trans[q][x], trans[p][x] = np ;
nq = f[p] ; if (len[np] <= 2) f[np] = fail[np] ;
else {
while (S[pos] != S[pos - len[nq] - 1] || len[nq] + 2 > (len[np] >> 1))
nq = fail[nq] ; f[np] = trans[nq][x] ;
}
}
last = trans[p][x] ;
}

这东西唯一的不同就是多了一个找 $fail’$ 的过程。首先如果当前的 $\rm len\leq 2$ 那么就应该是 $fail$(毕竟都是1个字母) ,否则就向上跳着找。

复杂度证明:因跳跳 $fail$ 的复杂度是对的所以跳 $fail’$ 也是对的(雾

值得注意的是:

1
while (S[pos] != S[pos - len[nq] - 1] || len[nq] + 2 > (len[np] >> 1))

这一句里第二个判断很容易写错。因为实际上我们跳的 $fail$ 是未扩展之前的,这一点从 S[pos] != S[pos - len[nq] - 1] 这一句就可以明显地看出来。所以如果要比较的话,应该 $+2$ 之后再比较。

于是为了水字数贴个代码:

1
2
3
4
5
6
7
8
9
int main(){
cin >> N >> (S + 1) ; P.Init() ; int i ;
for (i = 1 ; i <= N ; ++ i) P.Ins(S[i] - 'a' + 1, i) ;
// for (i = 1 ; i <= P.sz ; ++ i) cout << P.len[i] << endl ;
for (i = 1 ; i <= P.sz ; ++ i)
if (P.len[i] == (P.len[P.f[i]] << 1) && (P.len[i] % 4 == 0))
ans = max(ans, P.len[i]) ;
cout << ans << endl ;
}

其实本质上也不算一道难题,对吧?