全网第一！[FJOI2017] 回文子序列问题题解报告

TDoG_W · 2024-03-09 16:45:35 · 题解

题目历史地位

本题是 \texttt{FJOI} 历年 「绝世唐问、逆天神题」 中的一道，自 2017 年以来全网搜不到满分题解。本题是 D2T2，据说当年考场上无人满分，最高 90PTS。测评记录里基本都是套数据得到 100PTS。名副其实的 「OI 界未解之谜」。

本篇题解应该是全网目前能搜到的第一篇满分正解。

附赠 \texttt{FJOI} 唐问三剑客（不建议查看）

[FJOI2015] 带子串包含约束LCS问题
[FJOI2016] 所有公共子序列问题
[FJOI2017] 回文子序列问题

关于子序列自动机

看到又是 \texttt{FJOI} 的子序列问题，果断祭出子序列自动机。

考虑到本题的特殊性，这里重新介绍一下子序列自动机的构建与使用，它应该是最简单的自动机。

构建

子序列自动机（Subsequence Automaton，为防止和后缀自动机 SAM 名称冲突，简称 SSAM）实际上是一张子序列的 DAG，上面任意连续路径都是原串的一段子序列。

以下是一个例子，以FJOIAKIOI构建的子序列自动机：

如图每条边指向的是自己之后第一个出现这个字符的位置，据此可以想到一种构建方法：构建时我们可以从尾部开始反向构建，每次复制上一次的所有边，修改上个字符的出现位置。

乍一看好像很乱？没事，接下来一步步梳理。

以下是构建过程（蓝边表示继承的边，红边表示修改的边）：

Code

int Sub[N][M],tmp[M];

void build(int a[],int n,bool rev){
    memset(tmp,0,sizeof(tmp));
    for(int i=n;i>=1;i--){
        tmp[a[i]]=i;
        memcpy(Sub[i-1],tmp,sizeof(tmp));
    }
}

设有一串长 n,字符集为 \Sigma。

朴素构建 \mathcal O(n \lvert \Sigma \rvert)，单次查询 \mathcal O(1)。空间复杂度 \mathcal O(n \lvert \Sigma \rvert)。有时字符集较小，可以看成常数。

对于大型字符集，由于构建过程每个结点的连边最多只修改上一个结点连边的一条，实际上就是一个可持久化数组，主席树解决。

构建 \mathcal O(n \log \lvert \Sigma \rvert)，但单次查询退化至 \mathcal O(\log \lvert \Sigma \rvert)。空间复杂度 \mathcal O(n \log \lvert \Sigma \rvert)。

这个对解决本题帮助不大，不列代码了。

最长公共子序列

设有两串 A,B 长度分别为 n_1,n_2，求它们的最长公共子序列。

这个问题现在就转化为了 A,B 的子序列自动机的最长同构路径问题。使用动态规划解决，设 f_{i,j} 为 A 从 i 出发，B 从 j 出发，能走的最长同构路径，设 \Sigma_i 为结点 i 的所有存在转移边字符的集合，设 Sub_{i,k} 为从 i 结点出发，向字符 k 的转移边行走所到达的结点编号。综上，易得出转移式：

f_{i,j}=\max\limits _{k\in{\Sigma_i \cap \Sigma_j}}f_{Sub_{i,k},Sub_{j,k}}+1

答案就是 f_{0,0}，这里笔者用记忆化搜索实现，为了方便实现记忆化，所有答案加了一，最终需要减去。这里 m 是字符集大小。

int dfs(int x,int y){
    if(f[x][y])return f[x][y];
    f[x][y]=1;
    int u,v;
    for(int i=0;i<m;i++){
        u=SubA[x][i],v=SubB[y][i];
        if(!u or !v)continue;
        f[x][y]=max(f[x][y],dfs(u,v)+1);
    }
    return f[x][y];
}

ans=dfs(0,0)-1;

时间复杂度 \mathcal O(n_1 n_2 \lvert \Sigma \rvert)

对于更广义的最长公共子序列问题：m 个串的公共子序列，时间复杂度 \mathcal O(\lvert \Sigma \rvert \prod^m_{i=1} n_i )。其中 n_i 为 i 号串的长度。

例题：[TJOI2008] 公共子串（三串公共子序列问题）

最长回文子序列

设有一串长 n，求其最长回文子序列。

对原串的正反串分别建子序列自动机，跑最长公共子序列。

时间复杂度 \mathcal O(n^2\lvert \Sigma \rvert)

解题过程

那么本题非常明显了，对A、B串的正反串分别建子序列自动机，然后跑最长公共子序列。

同时发现字符集很大，但字符最多出现种数很少（最多只有 2 \times 500）。果断离散化。再加上状态数很多，有效状态很少，再使用 hash 表。

时间复杂度 \mathcal O(n^4\lvert \Sigma \rvert)。这个上界很松，跑不满。

然而笔者因为实现方式，被卡成 50PTS。

（接下来是笔者的漫长卡常之路）

终于卡到了 90PTS，此时笔者已经尝试无数种卡常方法。

实在没办法了，笔者开始考虑是不是算法本身有能优化的地方？

确实有，实际上笔者忽略了一个很关键的要点：「回文子序列」

回忆 Manacher ，猛然想到：实际上一个串自身的最长回文子序列只要比对一半就好了。这样最长回文子序列 \mathcal O(n^2 \lvert \Sigma \rvert) 就还要再乘一个 1 \over 2的小常数！

这里是最长回文子序列的改进示例，注意要特判奇回文：

Code

int dfs(int x,int y){
    if(x>n-y)return x==n-y+1;
    if(f[x][y])return f[x][y];
    f[x][y]=2;
    int u,v;
    for(int i=0;i<m;i++){
        u=SubPre[x][i],v=SubSuf[y][i];
        if(!u or !v)continue;
        f[x][y]=max(f[x][y],dfs(u,v)+2);
    }
    return f[x][y];
}

ans=dfs(0,0)-2;

那么 \mathcal O(n^4 \lvert \Sigma \rvert) \rightarrow \mathcal O({1 \over 4} n^4 \lvert \Sigma \rvert)，实际上比匹配四个串的最长公共子序列要快得多。

如果到这了，恭喜，\texttt{FJOI} 绝世唐问已被解决。

代码

为防止贺题er，代码放 Record 里。

极小概率（纯整活，仅供娱乐）：

后记

实际上笔者绕的弯路比此处展示的多得多，例如尝试卡光速读、手写 hashmap、玄学优化等等。感兴趣的可以看笔者的几页测评记录。

目前本题终于有满分题解了，可喜可贺。

如果本篇题解对您有帮助，请点个赞再走吧！如果没有帮助，也可以看在笔者幸苦写题解的份赏个赞吧！ ~~（也可以关注笔者嘤QWQ）~~

\red{最后，警示后人：如果你看见 \texttt{FJOI} 打头的题，请不要尝试去做。}

全网第一！[FJOI2017] 回文子序列问题 题解报告