algorithm - string1 中的最小长度窗口，其中 string2 是子序列

Question

给出了主要 DNA 序列(一个字符串)(比如说字符串 1)和另一个要搜索的字符串(比如说字符串 2)。您必须在 string1 中找到最小长度窗口，其中 string2 是子序列。
string1 = "abcdefababaef"
string2 = "abf"

我想到但似乎没有用的方法:
1. 使用最长公共(public)子序列 (LCS) 方法并检查是否(LCS 的长度 = string2 的长度)。但这会告诉我 string2 是否作为子序列出现在 string1 中，但不是最小窗口。
2. KMP算法，不知道怎么修改。
3.准备string2中string1的{characters: pos of characters}的map。喜欢: { a : 0,6,8,10
b : 1,7,9
f : 5,12
然后一些方法找到最小窗口并仍然保持“abf”的顺序

我不确定自己的思考方向是否正确，还是完全偏离了方向。
有没有已知的算法，或者有人知道任何方法吗？请提出建议。
提前致谢。

Answer 1

您可以执行 LCS 并使用 的 DP 表上的递归在 String2 的 String1 中找到所有最大子序列LCS 结果。然后计算每个LCS的窗口长度，你可以得到它的最小值。如果分支已经超过找到的当前最小窗口的大小，您也可以停止该分支。

检查读出所有LCS:-

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem