衝突的字符串編程競賽

Question

給定一組字符串，說

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

的問題是要找到，給出的字符串和允許的差異數數，一組字符串是否是一致的。

因此，與上述集，答案是「是」，如果我們允許一個單一的不一致字符串（第二個），但「否」如果我們允許任何不一致的字符串。

什麼是最好的算法，什麼是複雜性？

每一個解決方案，我想出要麼需要尋找每一個單個的組合，或者是完全錯誤的。例如，您不能僅僅通過並向字符串添加字符串（將不同的字符定義爲「不兼容」），因爲這樣**，ab廣告就會通過。

的實際問題（從）： 問題中號

在2417考古學家發現了一個大集合的重要他 - torical重視20世紀的文本文檔。雖然有許多重複的文件，它是作爲 以及損壞，由於時間很快就明顯發出很大的文本字跡，也有它們之間的一些disagree- 發言：。但是，人們注意到可以使文本組保持一致，即可以通過省略一些（少量）文本來實現文本之間的一致性。例如，文本：

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 

Answer 1

這感覺很隨和，所以我會略去一些細節。

A trie可以很好地處理這個問題。在給定文本包含*的任何索引處，都會使該文本從樹中的所有其他樹葉下降。然後你走這條線索，尋找任何匹配足夠文本的終端節點。

該trie最多有n * m節點，因此添加另一個文本是O(nm)。

構建這個trie也有一個複雜的問題。您必須按照正確的順序添加文本，並且必須檢查每個文本索引的正確順序。否則，最終可能會出現*b未包含在終端節點ab中的情況。但是這樣做不會引入任何進一步的算法複雜性。

總時間爲O(mn^2)。一旦構建完成，即可行走O(nm)，並且爲n節點添加節點爲O(nm)。

Answer 2

我建議你用一個字符串和一個計數表示一組一致的字符串。該字符串在一個位置上有一個字母，該位置中的任何字符串都有一個字母，否則就有星號。計數是集合中的字符串數量。所以{ab **，a * b *} = [abb *，2]。

與單個表示剛開始時，[* *，0]。

每次你看到一個字符串X時間：

1）添加[X，1]到組中的表示

2）。如果它與任何的陳述一致，到目前爲止，創建一個新的來自字符串和表示的表示 - 遞增計數，並且如果需要的話，修復字符串中的更多字母。將新的表示添加到一組表示。 3）如果你現在有多個具有相同字符串的表達式，那麼只保留一個表達式，用這個字符串的數量最多。

4）刪除表示的數量少於目前看到的字符串數量減去允許刪除的字符串數量。

5） - 從（1）與下一個字符串

在結束時，最合理的答案，如果有的話，是一個具有最大計數重複。任何一致的答案將被創建。任何時候手上的最大表示數是該階段可能答案的最大數量，即Choose（n，x），其中N是在該點看到的字符串的數量，x是您所在文本的數量允許丟棄。如果x = 1，這是n（n-1）/ 2。你必須這樣做n次，其他成本只隨着字符串的長度增長，所以我想你有一個O（mn^3）算法。