UndoHistory

作者：闫书弈 钟知闲

关键词：字符串 贪心

题目简述

你有一个编辑器，分为三个部分：文本缓冲区，结果窗口和撤销历史记录。文本缓冲区包含一个字符串（初始为空），结果窗口和撤销历史记录包含一个字符串序列（初始为空）。

你可以进行以下三种操作：

(1)在文本缓冲区中的字符串末尾添加一个字母，并将新字符串加入到撤销历史记录的末尾。代价为1。

(2)将文本缓冲区中的字符串加入到结果窗口的末尾，同时文本缓冲区不会改变。代价为1。

(3)将文本缓冲区中的字符串修改为撤销历史记录中的一个指定字符串。代价为2。

给定最终的结果窗口，你需要求出最小代价。

字符串数量<=50，字符串长度<=50，字符串只包含小写字母。

解法

依次考虑每个字符串如何构造出来。

(1)使用操作3。那么一定会撤销到先前出现过的最长前缀，然后一直使用操作1。

(2)不使用操作3。那么一定是从上一个字符串一直使用操作1。(此时要求上一个字符串是这个字符串的前缀)

由于这两种方法产生的撤销历史记录是等价的，直接贪心选取最优的即可。

实现方法

这里补充一下该解法如何实现。一种实现方法是使用 Trie 树，一开始 Trie 树 $T$ 只有一个根节点 $r$，在文本缓冲区的字符串 $s$ 添加字母的时候将 $s$ 对应的节点插入到 $T$ 中，则 $T$ 的节点集合恰好是历史记录的集合，因此从第 $i-1$ 个串 $s\_{i-1}$（最终结果窗口上的，这里假定 $s\_{-1}$ 为空串）转移到第 $i$ 个串 $s_i$ 时，将 $s_i$ 插入 $T$ 并在插入时记下 $T$ 中最深的属于 $s_i$ 前缀的节点 $x$，则：

(1)对于使用操作3的情况，$x$ 就是先前出现过的最长前缀，然后使用操作1的次数等于插入 $s_i$ 时新建的节点数；

(2)对于不使用操作3的情况，则要求 $x$ 在 $s\_{i-1}$ 对应节点的子树中，使用操作1的次数等于 $x$ 与 $s\_{i-1}$ 节点的深度差（事实上这个深度差不超过 $1$，否则不如(1)优）与插入 $s_i$ 时新建的节点数之和。

Trie 树并不难实现。设字符串数量为 $n$，字符串长度为 $l$，字符集大小 $\sigma = 26$，则复杂度为 $O(nl\sigma)$。

另一种实现方法是使用 C++ 的 STL 自带的 map（这也是原作者的方法）。用一个 map 来存所有出现在撤销历史记录中的前缀，做法和 Trie 树类似，对于每个串将其所有前缀插入 map，从 $s\_{i-1}$ 转移到 $s_i$ 时，枚举 $s_i$ 的前缀，在 map 中查询是否出现过即可。这个做法复杂度为 $O(nl^2\log nl^2)$，比 Trie 树复杂度差一些，优势在于不依赖于字符集大小。