题解 P4762 【[CERC2014]Virus synthesis】

· · 题解

回文自动机好题。

首先可以发现，操作 2 显然是越多越好。而我们发现，操作 2 之后产生了一个长度为偶数的回文串。由于不能拼接，最终答案一定是在一个长度为偶数的回文串基础上暴力添加得到的。

于是考虑建立 PAM，设 f_x 表示产生节点 x 代表的回文串的最小操作步数，l_x 代表节点 x 代表的回文串的长度，那么最终答案即为 \min\{f_x+n-l_x\}。

对于转移，首先可以发现，对于节点 x 对应的一个长度为偶数且不为 0 的回文串，如果在它两边添加一个相同的字符，可以得到节点 v 对应的回文串（相当于 PAM 上的一条边），那么 f_v=\min(f_v,f_x+1)。

证明：可以先构造 x 的一半，再加上两端的字符，最后执行一次 2 操作即可。

对于长度为 0 的情况，为了方便计算，设 f_0=1。

然后我们可以发现，一个回文串也可以通过操作 2 获得。于是我们维护一个 trans 指针，代表这个串最长的且长度不超过该串长度的一半的回文串所对应的节点。而这可以在插入时顺便求出，这里就不再讲了。

设 trans_x=p，可以得到转移：f_x=\min(f_x,f_p+\dfrac{l_x}{2}-l_p+1)。

然后根据上面的结论求出答案即可。时间复杂度 O(|S|)。

Code:

#include <bits/stdc++.h>
using namespace std ;
const int MAXN = 5e5 + 10 , INF = 0x3f3f3f3f ;
int T , n , fail[MAXN] , ch[MAXN][4] , dep[MAXN] ;
int las , tot , nw , tr[MAXN] , ans , f[MAXN] ;
int p[210] , q[MAXN] , hd , tl ;
char s[MAXN] ;
int gfail (int x) {
    for (; s[nw - dep[x] - 1] != s[nw] ; x = fail[x]) ;
    return x ;
}
void ext (int x) {
    las = gfail (las) ;
    if (!ch[las][x]) {
        dep[++tot] = dep[las] + 2 ;
        fail[tot] = ch[gfail (fail[las])][x] ;
        if (dep[tot] <= 2) tr[tot] = fail[tot] ;
        else {
            int tmp = tr[las] ;
            for (; s[nw - dep[tmp] - 1] != s[nw] || (dep[tmp] + 2) * 2 > dep[tot] ; tmp = fail[tmp]) ;
            tr[tot] = ch[tmp][x] ;
        }
        ch[las][x] = tot ;
    }
    las = ch[las][x] ;
}
int main () {
    scanf ("%d" , &T) ;
    p['A'] = 0 , p['C'] = 1 , p['G'] = 2 , p['T'] = 3 ;
    while (T--) {
        scanf ("%s" , s + 1) ;
        n = strlen (s + 1) ; ans = n ;
        fail[0] = fail[1] = 1 ; dep[1] = -1 ; las = tot = 1 ;
        for (nw = 1 ; nw <= n ; nw++) ext (p[s[nw]]) ;
        for (int i = 2 ; i <= tot ; i++) f[i] = dep[i] ;
        f[0] = 1 ; hd = tl = 1 ; q[1] = 0 ;
        while (hd <= tl) {
            int x = q[hd++] ;
            ans = min (ans , f[x] + n - dep[x]) ;
            for (int i = 0 ; i < 4 ; i++) {
                int v = ch[x][i] ;
                if (!v) continue ;
                //printf ("%d->%d\n" , x , v) ;
                f[v] = f[x] + 1 ;
                f[v] = min (f[v] , f[tr[v]] + 1 + dep[v] / 2 - dep[tr[v]]) ;
                q[++tl] = v ;
            }
        }
        //for (int i = 2 ; i <= tot ; i++) printf ("%d:%d\n" , i , f[i]) ;
        printf ("%d\n" , ans) ;
        for (int i = 0 ; i <= tot ; i++) {
            dep[i] = tr[i] = fail[i] = f[i] = 0 ;
            for (int j = 0 ; j < 4 ; j++) ch[i][j] = 0 ;
        }
    }
    return 0 ;
}