查找字符串出现的所有的行号在文本文件中

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'），然后只看这些行。

这是否是一种有效的策略取决于您的搜索的选择性和搜索字符串的长度等。只有测试才会显示该算法是否适合您的特定使用模式。