Google 面經求問

第一道题是不是可以先将树利用前序遍历序列化为字符串，这样两个相同的子树便是两个相邻的相同的子串，求出满足这个条件的最长的子串即可。第二题是杨氏矩阵，可以百度一下，除了这道题外，还有一题是在这种矩阵上序找第K大/小的值

burself 发表于 2016-8-13 13:32
这个类似用preorder遍历序列化二叉树，需要注意的是所有空节点也一定要序列化进去。
所以第一种情况是： ...

哦哦哦我明白你的意思了~ 我刚看到这题也在想要不要把子树变成 substring 然后转化成一个 substring 问题，但是没联系到序列化可以确定唯一 tree 上。

在 pre-order 把树序列化了之后，我们的问题就变成了 “寻找字符串 S 中，最长的 non-overlapping identical substrings”. 但是 KMP 的 failure function 貌似只针对在 pattern 每个位置上 fail 了之后回滚到哪里，找最长的后缀使得其与自身前缀匹配，在这个问题上，如果树的节点值有重复，并且叶节点的表示符号一致的话，有些可能的情况要考虑：

最长的两个 substring 在整个树序列化之后的中间位置;
最长的两个 substring 在我查的几个 O(n) 算法中都是可以互相 overlap 的，但是在这题中我们需要 disjoint;

相关问题的一个帖子：
http://codeforces.com/blog/entry/12810

顺着这个思路我貌似还没有查到复杂度上面比较好的做法。。不知道有没有更好的 idea

第一题是不是遍历，然后用最长公共字串解.