如何在O(nlogn+mlogm+k²)复杂度下求两数组最长公共连续子序列长度

我们有两个整数数组A[1..m]和B[1..n]，需要在时间复杂度O(nlogn + mlogm + k²)的要求下，求出它们的最长公共连续子序列的长度。其中k是满足A[x]=B[y]的(x,y)元组总数量。

示例输入1： #

A={1,2,3,4,5}
B={2,4,5,9,11,20}

输出：2

注意：数组不一定是有序的，以下是相关示例： #

示例输入2：

A={2,7,1,8,11}
B={1,3,7,1,11,2}

输出：2

内容的提问来源于stack exchange，提问作者Navid Naseri