任意两棵树的最大公共子结构

daisy8867

uuuouou 发表于 10-5-2015 11:02 AM
感觉可以用分治法来解决，复杂度最坏是O(M*N*min(M, N))的：

$ b& p. |& b5 W# g) @上面代码得到的是最大相同结构的节点集合， ...

& ~9 M2 \! k; s, }! Y; G# L! m4 h没有O(M + N)的办法吗，总觉得可以序列化后找最大公共子序列

uuuouou

daisy8867 发表于 10-6-2015 06:07 AM
6 H! q) D! \! |5 J" k  K, F没有O(M + N)的办法吗，总觉得可以序列化后找最大公共子序列

最长公共子序列的复杂度是O(M * N)呀，O(M + N)的想不出呢