查找給定位置文本中最短的唯一字符串

Question

還有什麼其他技術可用於查找text中確定的最短字符串，在確定的position處唯一，除了通過向position處的字符遞增添加字符的蠻力以及檢查唯一性？

爲了更好地解釋，

text = "word1 word2 word3" 

如果position = 9（在WORD2 R）; shortest_unique_at_pos = "rd2"。

小觀察，如果position = 13（w在word3中）;結果字符串應在兩個方向上搜索，所以shortest_unique_at_pos = "2 w"，而不是"word3"。當然，在交替方向時應用一些技術會產生所需的結果。

Answer 1

我假設您試圖避免的蠻力方法涉及對每個唯一字符串的「文本正文」進行多次迭代。可以用O(n)的前期費用來解決這個問題，其中n是文本的長度，然後每次搜索最短的唯一字符串時O(m*k)其中m是「唯一字符串」的長度，而k是次數文本中出現「確定索引」字母。如果您經常在大文本中搜索短的唯一字符串，這可能會有所幫助。

您可以事先創建一個字典，其中的鍵是「文本正文」中的字母，值是帶有索引的集，其中可以在文本中找到這些字母。例如，一個Python字典將如下所示：

indexes = { 'w': {0, 6, 12}, 'o': {1, 7, 13}, 'r': {2, 8, 14} } 

創建這樣的字典是一個O(n)操作。它可能更復雜，因爲內存被分配（重新）並且數據被複制，並且你得到了散列衝突，但是基本上你會遍歷文本一次，並在相應的索引集處添加一個字母的索引。您可以根據「文本正文」進行一次上述操作，並且每次搜索最短的唯一字符串時都要重複使用。

當您給出「確定的指數」例如2開始搜索：

1. 得到在當前索引i的信。例如'r'
2. 複製該字母的索引集以設置s例如從s e.g {8, 14}
3. 增量{2, 8, 14}
4. 移除i所有索引（1）在s例如{9, 15}
5. 得到i後面的下一個字母。例如'd'
6. 獲得指標集ns下一個字母
7. 如果s和ns不等於停止你已經找到了最短的唯一的字符串
8. 如果s和ns是從第4步

等於重複由於步驟4至8之間的迭代，複雜性與結果字符串的長度成比例。它也與s的大小成比例，該大小等於文本中從頭開始的字母的頻率。比較2組的等式具有與最小組大小成比例的複雜性。

在尋找更高效的算法時要注意權衡。對於短文本來說，蠻力實際上可能更好。如果您只搜索一次，上述方法的預付成本可能無意義。另外，它需要額外的內存。