Finding the line numbers of all occurences of a string in a text file
<p>I'm trying to write a function that does the following:</p>

<p>Given a text file, I want to find all occurences of a certain string in this file; then, for each occurence, the line on which it was found should be added to a list. We assume that each line only contains at most one occurence. The text file can get very large, which means a simple for-loop to iterate over each line the file will be too slow.</p>

<p>For example, say we have a file with the content:</p>

<ol>
<li>A B C D E F G</li>
<li>H J K L M N O</li>
<li>G F E D C B A</li>
<li>P Q R S T U V</li>
</ol>

<p>If I were to search for "A", the function would find it on lines 1 and 3 and thus add 1 and 3 to a list (and then return the list).</p>

<p>I was considering binary search, but it seems to require that a list to be sorted and the elements to be distinct - I'm looking for identical values.</p>

<p>So, is any other search algorithm i can base my function on, with roughly the same performance as binary search?</p>

<p>Thanks!</p>
