0

给定一组字符串，比如说

ap***
ab*le
a****
ab***

问题是在给定字符串数量和允许差异的数量的情况下，找出一组字符串是否一致。

因此，对于上述设置，如果我们允许单个不一致的字符串（第二个），答案是“是”，但如果我们不允许不一致的字符串，则答案是“否”。

什么是最好的算法，复杂度是多少？

我提出的每一个解决方案要么需要查看每一个组合，要么就是错误的。例如，您不能只通过并将字符串添加到集合（将 distinct 定义为“不兼容”），因为那样 **, ab ad 将通过。

实际问题（来自 ）：问题 M

2417 年，考古学家发现了大量具有重要历史意义的 20 世纪文本文件。尽管有许多重复的文件，但很快就很明显，除了由于时间造成的损坏使大部分文本难以辨认外，它们之间也存在一些分歧。然而，注意到可以使文本组保持一致，即可以通过省略一些（少量）文本来实现文本之间的一致性。例如，文本：

ap***
ab*le
app*e
*p\**e

（其中 * 表示难以辨认的字符）可以通过仅删除第二个文本来保持一致。

输入将由一系列文本集组成。每个集合都以一行开始，指定集合中的文本数量，以及可以删除的最大文本数量。接下来是单独的文本，每行一个。每个文本由至少一个且不超过 250 个字符组成，可以是小写字母或星号。一组中的所有文本将具有相同的长度，并且一组中的文本不会超过 10,000 条。集合序列由包含两个零 (0 0) 的行终止。

每个集合的输出由包含单词“是”或“否”之一的行组成，具体取决于是否可以通过最多删除指定数量的文本来使集合保持一致。

Sample input
4 1
ap***
ab*le
app*e
*pple
3 1
a
b
c
4 2
fred
ferd
derf
frd*
0 0

Sample output
Yes
No
No
4

2 回答 2

1

这感觉像家庭作业，所以我将省略一些细节。

一个trie可以很好地处理这个问题。在给定文本包含 的任何索引处*，您可以使该文本从 trie 中的所有其他叶子下降。然后你走特里，寻找任何匹配足够文本的终端节点。

trie 最多有n * m节点，因此添加另一个文本是O(nm).

构建 trie 也有一个复杂的问题。您必须以正确的顺序添加文本，并且您必须检查每个文本索引的正确顺序。否则，您最终可能会遇到*b不包含在终端节点中的情况ab。但这样做不会引入任何进一步的算法复杂性。

总时间为O(mn^2)。一旦构建好就走树O(nm)，添加节点是O(nm)为了n节点。

于 2012-08-15T13:08:43.207 回答
0

I propose that you represent a set of consistent strings with a string and a count. The string has a letter at a position where any of the strings in the set has a letter, and an asterisk there otherwise. The count is the number of strings in the set. So {ab**, a*b*} = [abb*, 2].

Start off with a single representation, [**,0].

Each time you see a string X:

1) Add [X,1] to the set of representations

2) If it is consistent with any of the representations so far, create a new representation from the string and the representation - increment the count, and if necessary fix some more letters in the string. Add the new representation to the set of representations.

3) If you now have more than one representation with the same string, keep just one, with the count the maximum of those with that string.

4) Remove representations whose count is less than the number of strings seen so far minus the number of strings you are allowed to leave out.

5) - repeat from (1) with the next string

At the end the most plausible answer, if any, is the one with the largest count. Any consistent answer will have been created. The maximum number of representations on hand at any one time is the maximum number of possible answers at that stage, which is Choose(n, x) where N is the number of strings seen at that point and x is the number of texts you are allowed to discard. If x = 1 this is n(n-1)/2. You have to do this n times, and the other costs grow only with the length of the string, so I guess you have an O(mn^3) algorithm.

于 2012-08-15T04:47:20.370 回答