String search algorithm for finding if a long list of long strings string exists in a similarly sized haystack
In the post you write:


  I also believe the in operator is inefficient because it is using the naïve method of searching the string.


But if you look at the implementation of Python's in operator for strings, you find that it calls the FASTSEARCH function, which is "based on a mix between Boyer–Moore and Horspool".

The problem of searching many times for strings in a collection of documents is known as full-text search. The approach in the post is to search for the string in each document in turn: this scales linearly with the number and length of the documents. To improve on this scaling behaviour, you need to preprocess the collection of documents into an index. (Note that this only helps if you are searching many times—if you are searching only once, then you can't do better than searching each document.)

Here's a simple demonstration of the full-text search approach:

from collections import defaultdict

class SearchIndex:
    "A full-text search index."

    def __init__(self):
        # Mapping from word to set of documents containing that word.
        self._index = defaultdict(set) 

    def add(self, document):
        "Add document to the search index."
        for word in document.split():
            self._index[word].add(document)

    def search(self, query):
        "Generate the documents containing the query string."
        candidates = min((self._index[word] for word in query.split()), key=len)
        for document in candidates:
            if query in document:
                yield document


This works by building a mapping from words to the sets of documents containing each word (an "inverted index"). When a document is added to the index, it is split into words by calling str.split, and the document is added to the mapping for each word. This is conveniently implemented using collections.defaultdict. 

To search for a string, the string is also split into words, and the index consulted for each word. The rarest word (the one mapping to the fewest number of documents) is used to get a set of candidates, and then each candidate is searched for the entire string.

This is a very simple approach and there are many refinements you can make. In particular, if you are going to be making queries of the same set of documents over a long period of time then you will want to make your inverted index persistent, and for that you will want a full-text search engine or database.