String search algorithm for finding if a long list of long strings string exists in a similarly sized haystack My use case is that I have a list of emails and I need to find if the email is in the chain:

emails = [
    ['    RE: I just got your test || This is a top level email roughly 300+ words in length on average'],
    ['RE:RE: Something | RE: Something | This is another entirely distinct email that is the top level'],
    ['RE: FooBar | A third email that is entirely distinct']
    ... #performance issues start occurring with emails growing to &gt; 50 items
]


Now I would search for an email which is a reply:

test_email = """
A third email that is entirely distinct
"""


Currently I am using a KMP type search but I believe this is inefficient because it searches for multiple copies of the needle. I also believe the in operator is inefficient because it is using the niave method of searching the string.

An implementation of KMP in python I found and modified slightly:

class KMP:
    @classmethod
    def partial(self, pattern):
        """ Calculate partial match table: String -&gt; [Int]"""
        ret = [0]

        for i in range(1, len(pattern)):
            j = ret[i - 1]
            while j &gt; 0 and pattern[j] != pattern[i]:
                j = ret[j - 1]
            ret.append(j + 1 if pattern[j] == pattern[i] else j)
        return ret

    @classmethod  
    def search(self, T, P):
        """ 
        KMP search main algorithm: String -&gt; String -&gt; [Int] 
        Return all the matching position of pattern string P in S
        """
        partial, ret, j = KMP.partial(P), [], 0

        for i in range(len(T)):
            while j &gt; 0 and T[i] != P[j]:
                j = partial[j - 1]
            try:
                if T[i] == P[j]: j += 1
            except:
                return False
            if j == len(P): 
                return True
        return False


Used here:

for choice in choices: #choice[0] is email in the reply chain
    if current_email == choice[0]:
        incident_type = choice[1]
        break
    elif len(current_email) &gt; len(choice[0]):
        if KMP.search(current_email, choice[0]):
            incident_type = choice[1]
            break
    else:
        if KMP.search(choice[0], current_email):
            incident_type = choice[1]
            break


Should I fix this implementation or scrap it in favor of another algo?
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.