找到最长的序列S即是A，B，C字符串中的子 [英] find the longest sequence S that is a subsequence of A,B,C string

问题描述

给出一个多项式时间算法，采用三根弦，A，B和C，作为输入，并返回最长的序列S是一个序列A，B和C。

Give a polynomial time algorithm that takes three strings, A, B and C, as input, and returns the longest sequence S that is a subsequence of A, B, and C.

推荐答案

让 DP [I，J，K] = $ P $的最长公共子pfixes A [1..i]，B [1..j]，C [1..k]

我们有：

dp[i, j, k] = dp[i - 1, j - 1, k - 1] + 1 if A[i] = B[j] = C[k]
              max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise

类似于2d的情况下，除有3个维度。复杂性是 O（LEN A * LEN B * LEN C）。

这篇关于找到最长的序列S即是A，B，C字符串中的子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！