原问题
昨天一个同学问了我一个问题，他想扩展 JavaScript 中的 Array.prototype，以判断当前数组是否被包含于另一个数组（不考虑 a = [a] 这样的循环引用），例如：[1] 被包含于 [2, [1], 3] 和 [[2], [3, [1], 4]] 两个数组中。其实这道题如果只需要考虑引用相等，例如这样设计测试用例：
const a = [1];
const b = [2, a, 3];
console.log(a.isPartOf(b)); // => true那就比较容易了，如果对 JavaScript 比较熟悉的话，应该可以快速写出如下的代码：
Array.prototype.isPartOf = function (other) {
const isPartOf = (self, other) => {
for (const item of other) {
if (item instanceof Array) {
if (self === item || isPartOf(self, item)) {
return true;
}
}
}
return false;
}
return this === other || isPartOf(this, other);
};然而换个样例：[1].isPartOf(b)，如果想让它为 true，上面的代码就要改改了，方法是将中间的 self === item 改为 deepEqual(self, item)，于是这个问题就解决了。
deepEqual 既然涉及到了递归，那肯定对于一些数据会存在大量无用的比较，例如每次比较都是挂在了“最后的某一层多/少了一个元素”上，算法时间复杂度就退化的很厉害。有没有什么办法可以优化一下呢？
第一次优化
其实原因很简单，由于是基于递归，所以没法提前知道下一层数组有多长，但是如果事先将数组用 flattern 拍平为序列，就很容易知道。至于是否能匹配到，直接用字符串匹配常用的 KMP 算法就可以了！还可以优化一下 next 数组让其失配的时候多跳几格。
但直接拍平是会有问题的，因为 [1, [2], 3] 和 [1, 2, 3] 会被转换为同一个序列，因此就要加上与递归相关的一些信息，例如在递归下去的时候输出一个 ↓ 符号，在回溯的时候输出一个 ↑ 符号。虽然看起来是显然的，但我并不会证明……
于是去高中竞赛群里问了一下这个转换是不是唯一的，然后就被群里的大佬们鄙视了一顿，说“你直接用括号序列不行么”，我一听好有道理啊！果然几年不写算法水平是会退化很多的。
第二次优化
上面的方法看起来似乎有点可行，但是每次失配之后跳的时候，可能脸比较黑，不巧跳到了某个不是数组的地方，例如：
主串: 2 ( 1 ( 2 100 ) )
子串: 2 ( 100 )这里主串的 2 是一个普通的 Number，并不是数组，虽然可以通过特判来避免比较，但我想直接跳到数组的地方去比较。于是可以在构造括号序列的时候，记录一下“下一个数组开头”的位置（一定是一个数字或者是一个结束的哨兵），每当失配的时候就跳到 Math.max(记录的这个位置, next 对应的位置) 上，可能可以多跳一些距离。
此外递归的时候还可以顺便还可以记录一下“当前数组结尾的位置”（一定是一个括号），如果当前主串的匹配窗口的末尾不是“当前数组结尾的位置”，就可以直接当成失配跳走了。
回归本质
后来才发现我被自己一开始的思路带偏了。字符串的优化固然有效，但其实问题并没有那么麻烦。嵌套的数组本质上是一棵树（只需要给每个数组加一个值相同的虚拟的根节点即可），问题的本质是“问一棵树是不是另一棵树的子树”，进一步来说，就是比较某一棵给定的树是否跟森林中的某棵树相等。
这样一来，第一次优化是不用做的，第二次优化的替代方法也很简单：
- 记录“下一棵子树的位置”，如果失配则直接跳到下一棵子树。
- 当前子树匹配之前先比较子孙数量（可以在预处理中记录），如果子树的子孙数量多于给定树的子孙数量，就递归进去比较，若相等则直接比较。
不过可能优化的稍微差了一点，毕竟带上括号之后，序列长度有一部分是跟子树结构相关的，如果只是比较子孙数量的话，很容易构造出一棵子孙数量相同但结构完全不同的树。
当然，想要实现跟之前一样的优化是可以的，方法依旧是在递归的时候生成括号序列，不同的是只需要在每个子树根节点记录一下所在子树的序列长度即可，无需生成整个序列。比较的时候同时比较子孙数量和括号序列长度。
这样的话，随着子树规模的扩大，一次可以跳过的位置也就越多。但是需要注意的是，由于预处理需要一定的时间，因此这个优化只适合“频繁查找、少量修改”的情况。毕竟修改一次需要 O(logN) 的时间来调整预处理的结果呢！