最小表示（字符串和树）学习笔记

字符串的最小表示法

由来

字符串有时需要进行“旋转”，即一个一个把尾部元素放到前面。那么，我们怎么知道一个字符串是不是另一个字符串旋转过来的呢？
我们发现，这种旋转其实相当于把字符串首尾相接成环，然后取不同的起点重新组成字符串。在这些能够组成的字符串中，字典序最小的字符串是唯一的。那么，我们能不能在两个字符串中分别找到能旋转到的字典序最小的字符串，进行比对呢？
如果我们知道了一个字符串，那么它所能构成的环就是唯一确定的，所以，我们可以遍历一遍这个环，枚举起点，找到字典序最小的字符串。这也说明，这个字典序最小的字符串唯一对应一个字符串环，一个字符串环唯一对应一个字典序最小的字符串。我们就可以把这个字典序最小的字符串看成这个环能构成的所有字符串的身份证，如果这个身份证相同，那么这两个字符串一定能够用旋转操作互相得到。
因为这个字符串是一个字典序最小的字符串，我们就叫这个字符串为环能构成的所有字符串（也叫循环同构串）的最小表示法。它其实在表示字符串的一种属性。
求法

我们上面已经说了，求字符串的最小表示法的方法是遍历这个环，找到字典序最小的字符串。环的处理可以断环为链，看每个起点后面的字符串。
\(O(n^2)\) 暴力做法

那么一种显然的暴力就出现了，枚举起点，记录下当前遍历到的字典序最小的字符串，进行比较，然后更新最小的字符串。
由于枚举起点是 \(O(n)\)，字符串比较是 \(O(n)\)，所以总体时间复杂度是 \(O(n^2)\)。
\(O(n)\) 做法

上述算法，其实最慢的地方在字典序比较，而枚举起点也有一种常用的优化算法——双指针。

在上图中，每一个圆圈表示字符串中的元素，这个序列是断环为链完了的结果。\(i\) 和 \(j\) 是枚举的起点，\(k\) 是起点开始的对应下标（\(k\) 严格小于字符串的长度）。假设 \(i —— i + k - 1\) 这个子串与 \(j —— j + k - 1\) 这个子串完全一致。
如果 \(i + k\) 对应的元素大于 \(j + k\) 对应的元素，那么我们知道以 \(i\) 为起点的字符串的字典序就一定比以 \(j\) 为起点的字符串的字典序要大，因此以 \(i\) 为起点的字符串就不可能是答案。同理，如果 \(k \ge 1\)，那么以 \(i +1\) 为起点的字符串也不可能是答案，因为这个字符串的字典序一定比以 \(j + 1\) 为起点的字典序要大。这样下去，对于任意 \(0 \le u \le k\)，都有以 \(i + u\) 为起点的字符串不可能是答案。因此，我们可以直接让 \(i\) 这个指针跳到 \(i + k + 1\)。同理，如果 \(i + k\) 对应的元素小于 \(j + k\) 对应的元素，我们就可以让 \(j\) 跳到 \(j + k + 1\)。
跳完之后，如果两个指针相等了，就任意加 \(1\)；如果任意指针超过了原字符串的长度，那么整个循环就结束了。此时两个指针中较小的那个就是最小表示法对应的起点（另一个越界了）。
由于 \(k\) 最小是 \(0\)，所以两个指针最多最多跳 \(2n\) 次，\(k\) 的枚举最多 \(4n\) 次，因此总计算量最多是 \(6n\) 次，也就是 \(O(n)\) 的时间复杂度。
这种双指针（或者应该是三指针）跳动的方法在各种问题中都有可能遇到，如果我们能够判断跳动区域一定不可能是答案或者数据不再有用，我们就可以跳过，在 \(O(n)\) 的时间复杂度内完成整个算法。
示例代码：

1. void get_min(string &a)
2. {
3.     static string tmp;
4.     tmp = a + a;
6.     int i = 0, j = 1, k;
7.     while (i < a.size() && j < a.size())
8.     {
9.         for (k = 0; k < a.size() && tmp[i + k] == tmp[j + k]; k ++ );
10.         if (k == a.size()) break;
11.         if (tmp[i + k] > tmp[j + k])
12.         {
13.             i += k + 1;
14.             if (i == j) i ++ ;
15.         }
16.         else
17.         {
18.             j += k + 1;
19.             if (i == j) j ++ ;
20.         }
21.     }
22.     k = min(i, j);
24.     for (i = 0; i < a.size(); i ++ ) a[i] = tmp[k + i];
25. }

复制代码

练习：雪花雪花雪花 项链
树的最小表示

上面已经说过，最小表示的核心就是在于字典序最小，可以让整个序列唯一，作为两个序列的身份证。现在我们来考虑下面这个问题：

给定两个树的 dfs 序，判断这两个树是否为同一颗树。

我们先来发现 dfs 序的一些性质，遍历到节点 \(i\) 时，我们首先把 \(i\) 加入序列中去，然后遍历所有儿子，最后回到这个节点，再把 \(i\) 加入序列。也就是说，两个 \(i\) 中间的都是 \(i\) 的儿子序列，这使得这颗以 \(i\) 为根的子树序列是相对独立的，它的儿子子树序列也是相对独立的；或者说，具有最优子结构，可以贪心。具体怎么贪心呢？假设我们已经得到了以 \(i\) 的所有儿子为根的子树的最小表示，现在要得到以 \(i\) 为根的子树的最小表示，我们就应该把所有的儿子序列排排序，把字典序小的提到前面去，然后依次排开，用 \(i\) 包裹，这样就得到了以 \(i\) 为根的子树的最小表示。感性理解一下，\(i\) 的父节点的所有子树也这样处理，应该就能得到以它为根的最小表示……这样我们就能得到整棵树全局的最小表示了。
可能还是不好理解，所以直接上代码：

1. string dfs(const string &str, int &u)
2. {
3.     char c = str[u];
4.     u ++ ; //进入这个节点
5.     vector<string> seqs;
6.     while (str[u] != c) seqs.push_back(dfs(str, u)); //遍历子树
7.     u ++ ; //出这个节点
8.    
9.     sort(seqs.begin(), seqs.end());
10.   //求答案
11.     string res;
12.     res += c;
13.     for (auto s : seqs) res += s;
14.     res += c;
15.     return res;
16. }

复制代码

例题：树形地铁系统
总结

最小表示，就是把多种多样的可能序列，转化为唯一确定的字典序最小的序列，作为比较的身份证明。
PS：可能有人会发现这两份代码与 yxc 大佬的比较相似，我就改了一点。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！