模板最长公共子序列nlogn

关于最长公共子序列问题的时间复杂度为O(nlogn)的算法模板
对于给定两个长度分别为m和n的字符串X和Y，计算其最长公共子序列(LCS)，通常的方法是采用时间复杂度为(O(m \times n))的动态规划方法。然而，在特定情况下可以实现更高效的解决方案。
当处理的是排列而非一般字符串时，即输入数据由不重复整数构成并代表某种顺序，则存在一种基于二分查找技术来达到(O((m+n)\log m))[^1]效率级别的改进型解法。此方法首先映射其中一个序列为连续区间内的数值以便后续操作；接着利用另一个序列中的元素在此已调整过的序列上执行类似于最长增加子序列(Longest Increasing Subsequence, LIS)的操作流程完成匹配过程[^2]。
具体来说：

将第一个排列 (P_1) 映射到位置索引；
对第二个排列 (P_2) 中每一个值查询它在 (P_1) 中的位置，并记录这些位置形成的新列表；
使用上述新列表作为基础去解决一个等价版本的最大增长子串问题——这一步骤能够通过树状数组或线段树等方式加速至 (O(N\log N)) 时间内完成[^3]。

以下是Python代码示例展示如何应用这一思路解决问题:
from bisect import bisect_left

def map_positions(p):
pos = {value: index for index, value in enumerate(p)}
return [pos[value]+1 for value in p]

def lis(nums):
dp = []
for num in nums:
i = bisect_left(dp, num)
if i == len(dp):
dp.append(num)
else:
dp[i] = num
return len(dp)

def lcs_via_lis(p1, p2):
mapped_p2 = map_positions(dict(enumerate(p1)))
positions_in_p1 = [mapped_p2[p] for p in p2 if p in mapped_p2]

return lis(positions_in_p1)

p1 = [3, 2, 1, 4, 5]
p2 = [1, 2, 3, 4, 5]
print(lcs_via_lis(p1, p2))
登录后复制