如果我有两个序列(比如字符串)
// 01234567890123456789012
a = "AAACDDFFFEE1122VV1VAADD"
// 0123456789012345678901
b = "DDFFAA11221DHHVV1VAAFE"
我想知道从 b 到 a 的最佳子串匹配(无序)，例如:
optimal (6 matched parts, 19 characters of a matched)
b a
DDFF -> DDFF (4,7)
AA -> AA (0,1)
1122 -> 1122 (11,14)
1
D -> D (21)
HH
VV1VAA -> VV1VAA (15,20)
FE -> FE (8,9)
还有另一种解决方案，但不是最优的:
not optimal (8 parts matched, 19 characters of a matched)
b a
DDFF -> DDFF (4,7)
AA -> AA (0,1)
1122 -> 1122 (11,14)
1 -> 1 (17)
D -> D (21)
HH
VV -> VV (15,16)
1
VAA -> VAA (18,20)
FE -> FE (8,9)
对于这个问题，什么样的算法比较好？？？ (我需要最佳结果，性能至关重要)。
谢谢。
最佳答案
有趣的问题，您可以使用 Boyer-Moore (http://en.wikipedia.org/wiki/Boyer –Moore_string_search_algorithm) 或 KMP (http://en.wikipedia.org/wiki/Knuth –Morris–Pratt_algorithm) 算法在 O(|a|.|b| + |b|^2) 中解决它或任何其他线性时间字符串搜索算法。
- 对每个 b[0..i] ty 在字符串 a 中(在 O(|a| + i) 中)找到它，直到找不到为止
- 你知道你可以找到 b[0..i] 而不是 b[0..i+1]，所以你有一个 b[0..i] 的匹配，然后你继续 b[i+1。 .i+1],b[i+1..i+2]..
- 最后判断b的每一部分是否匹配，如果匹配则尽可能大。
总复杂度最多为 sum( O(|a| + i) , i=0..|b|) = O(|a|.|b| + |b|^2) 但它可以是很多如果在 a 中只能找到 b 的小子串，则更小。
编辑:
上面的做法是贪心的，不会最小化部分的数量，但我认为它会最大化匹配的字符总数。
关于最佳解决方案的想法:
- 对于|b| 的每个|b|^2 个子串判断是否可以在|a|中找到，只保留符合条件的
- 我们需要在这些字符串中找到它们的一个子集:
- 其中任何两个之间没有重叠
- 长度之和最大
- 等长，字符串个数必须最少
总和很容易计算，因为一个非常简单的解决方案是只匹配大小为 1 的子字符串:那么长度就是 a 和 b 之间的公共(public)字母数。
因此，如果我们将 b 的大小为 1 的子字符串(即使是不在 a 中的字母)添加到上面的匹配字符串集合中，我们需要找到 b 的最小集合覆盖且没有重叠。
一般的集合覆盖是 NP 完全的，但这里有不重叠的约束，这有帮助吗？
我正在研究它。
确实，NP 完全:http://www.springerlink.com/content/n73561q050w54pn6/
您可能想要寻找近似算法....
关于algorithm - 对于无序序列匹配问题，什么样的算法比较好？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3889722/