首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

最长公共子序列与最长公共子串

最长公共子序列 举个例子:s1="abcfde",s2="bcde"。那么s1与s2的最长公共子序列就是"bcde",注意不要求连续。该问题是典型的动态规划问题。...(i, j)从0开始,那么递推关系很容易找到:(maxLen(i,j)表示s1字符串左边i个字符构成的子串与s2左边j个字符构成的子串的最长公共子序列长度,下同) if(s1[i-1] == s2[j-...最长公共子串与上述最长公共子序列不一样,最长公共子串要求连续。...例如s1="asdfddsx",s2="asssdfed",那么s1与s2的最长公共子串是:"sdf"。...最长公共子串的输出比上面最长公共子序列简单,因为后者一定是连续的,我们只要保存最后一个两个字符串字符相等的位置index,以及最长公共子串的长度length,然后从index位置往回倒推index个字符即可

97310

最近公共祖先LCA

最近公共祖先(Lowest Common Ancestors,LCA)指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。...u和v的公共祖先指一个节点既是u的祖先,又是v的祖先。u和v的最近公共祖先指距离u和v最近的公共祖先。若v是u的祖先,则u和v的最近公共祖先是v。 可以使用LCA求解树上任意两点之间的距离。...2.同步前进法 将u、v中较深的节点向上走到和深度较浅的节点同一深度,然后两个点一起向上走,直到走到同一个节点,该节点就是u、v的最近公共祖先,记作LCA(u,v)。...此时x、y的父节点为最近公共祖先节点,即LCA(x, y)=F[x][0]。 完整的求解过程如下图所示。...此时x、y的父节点为公共祖先节点。

82210
领券