读论文系列 #1——串与 DAG 的 LCS

· · 算法·理论

前天 @changruinian2020 发了我一篇论文，让我帮他读读。以前基本上没有在毫无相关理论准备的情况下读论文，这里记录一下，挺有帮助的。链接。

首先这篇论文在 OI 范围内没啥意义，纯粹就是练阅读能力，相对一些其他论文来说比较友好。如果您也想练习，推荐先去看原文，再对照一下下面提供的我的理解（不保证正确）。

问题：给定一张 DAG G，点上带有字符串 \ell(v)，给定串 Q，求 Q 与 G（的所有路径中）的 LCS，一条路径对应的串就是点的串顺次拼起来。

结构：求得每个单点 v 与 Q 的所有极长公共子串 MEM（说是可以关于 MEM 个数线性地求出，在另一篇论文里。记为 N 个），记作 (Q[x\cdots x+\kappa-1],\ell(v)[i\cdots j])，然后选出一个 MEM 序列，要求 x\le x',v\rightsquigarrow v'，允许 v=v'，如果这样有额外的条件 i\le i'（这里加一撇表示序列中的下一项）。这个时候把这个序列在 Q 和所有涉及到的 \ell(v) 中都划出对应匹配的子串，如果相邻两个 MEM 在 Q 中或者某个 \ell(v) 中划的线有重合，就把前面的一个区间缩一下（Q 和 \ell(v) 同时缩）。这样子得出的公共子序列一定能考虑到最优解。例子可以参见 Figure 1。

求解：

  1. 先考虑每个点只能选一个 MEM 的情况，那么只能在 Q 中出现划线重合。这个问题相当于：G 中每个点都挂了一些区间，要选一条路径，路径上的每个点选挂在上面的 0 或 1 个区间，得到 [l_1,r_1],\cdots,[l_t,r_t]，其中要求 l_i\le l_{i+1}。现在最大化 \sum(\min(r_i+1,l_{i+1})-l_i)。由于可能是在 DAG 上跳着走，所以有点难搞。给所有挂着的区间一起编个号，记 dp[i] 表示 i 号区间作为最后一个区间的答案。通过另一个神秘算法找到图的最小（可相交）路径覆盖（记为 k 条），每一条路径统一更新其他所有点（对于每个希望被更新的点，找到路径上最后一个可达它的点，在那个点处理完时更新，这样就避免了后效性），然后就剩下路径内部转移了。具体统一更新的方法就是讨论 \sum 里的 \min 取哪一项，就变成了一个单点更新，求区间 \max 的问题了，每条路径维护两棵线段树/平衡树即可。这样就是 \mathrm{O}(kN\log N) 的。
    补充一句，斜体部分在原文中说若要做到与 \lvert E\rvert 无关得用 transitive reduction，这个东西看起来有些前途，NOI2021D1T3 用到了这个思想。

  2. 然后要考虑点内部选多个 MEM 的情况。先考虑两个串之间的问题，仍然是已知两者的所有 MEM。这里我认为论文有笔误，显然 M.sort() 应该按照 i 而不是 x 排序。转移就按照 coverage 公式讨论：a. 两者都不重合；b. T 中不重合 Q 中重合（与第一步中类似）；c. T 中重合且比 Q 中重合得多（允许 Q 不重合）；d. T 中重合且比 Q 中重合得少。值得思考的是：① 为什么不能将 bd 合并成 T 中重合得且比 Q 中重合的少（允许 T 不重合）？因为这时要保证 Q 中有重合，那就有两维限制，无法维护。② 为什么 d 无需考虑 x 递增条件不满足的情况？因为这个在后续转移中一定不会成为最优解。

  3. 综合起来，2 中的 ab 情况和 1 的点间更新是兼容的，不用额外转移了。

这里最感到奇怪的就是这个 MEM 的引入以及链覆盖的做法。现在理论界确实有很多 parameterized 的解法（主要理论下界都被研究完了），即关于输入的某个示性数较优的解法。OI 中这类情况就较少。

然后是一些闲话。

形式化是一把双刃剑，保证了严谨性的同时给没有相关基础的读者竖起了一面妨碍理解的高墙。vuq 也讨论过“知识的诅咒”这一问题。当你会了一个模型时，你可以任意地把它形式化地表述出来，但是读者初步看了之后，不懂的还是不懂，因为他们看不到你的文字背后的思考过程（而且实际表述顺序很可能相对于思考顺序是颠倒的），你的 motivation 和 intuition，在理论体系上是怎样的存在（本质、意义、等价表述），当然也包括 vuq 里提到的联想知识；甚至单纯就是被一堆定义绕晕了，就放弃了。我以前看算法导论和部分集训队论文就是这种感觉，就像看别人的代码一样。

但是论文都得保证严谨性。友善的作者可能会加入例子和非形式化解释，但不多。那我硬啃的过程就是把它变成自己的理解，我觉得关键就是在明确定义的前提下尽量带入自己的思路，尝试还原作者的想法。如果硬着头皮逐字逐句地去看文章，被动地理解，会很痛苦（很多情况下就是莫名其妙提出来一个 theorem 然后证明），而且无法收获思维上的营养。读的过程中要经常停下来，想象目前模型的图形化解释、例子以及如果我面对这个模型，我会怎么考虑。主动地去思考，会比较好。当然前提是核心 definition 和问题模型得先搞清楚，如果发现定义不自洽可以检查一下是不是有些专业表述望文生义了。一些无关紧要的延伸的定义也没必要抠得很明白。当然也没法 100% 搞清背后的动机，毕竟都是基于先前已有的论文成果往上堆。

欢迎讨论。