查找字符串出現的所有的行號在文本文件中

Question

我想寫執行以下功能：

給定一個文本文件，我想找到一個特定字符串的所有出現在這個文件;那麼，對於每一次發生，它被發現的行應該被添加到列表中。我們假設每行只包含至多一個事件。文本文件可能變得非常大，這意味着一個簡單的for-loop循環遍歷每行文件將會太慢。

例如，假設我們有內容的文件：

1. ABCDEFG
2. HJKLMNO
3. GFEDCBA
4. PQRSTUV

如果我要搜索 「A」 ，函數會在第1行和第3行上找到它，從而將1和3添加到列表中（然後返回列表）。

我正在考慮二元搜索，但它似乎要求將一個列表進行排序，並將元素分開 - 我正在尋找相同的值。

那麼，是否有其他搜索算法可以基於我的功能，其性能與二分查找大致相同？

謝謝！

Answer 1

您可以爲您的線索引，如果它們不經常更換，您將對它們執行許多搜索。索引它們的一種方法是創建一個直方圖，其中的字符出現在哪些行（以及可能有多少次）中。然後你可以反轉這個，並說例如字母A出現在第5,10和20行。如果你正在搜索「ABF」，你可以使用反轉的直方圖來確定哪些行是候選者（即包含字母'A'，'B'和'F'），然後只看這些行。

這是否是一種有效的策略取決於您的搜索的選擇性和搜索字符串的長度等。只有測試纔會顯示該算法是否適合您的特定使用模式。