反向最长公共子序列

📘 题目描述

给定两个长度分别为 $n,m$ 的序列 $a,b$，构造一个最短的序列，使得 $a,b$ 都是它的子序列。字符串长度 $1\leq n,m\leq 1000$。

💡 解题思路

构造序列 $c=a+b$ 是一个合法的可行解，其长度为 $n+m$。但不一定保证最短。

公共子序列只需要出现一次，因此答案为 $n+m-\text{LCS(a,b)}$。