Efficient substring match

Question

I have a list of unique strings (approx 2500000) of different lengths and I am trying to find if there is any string which occurs as a substring of previous strings.

def index_containing_substring(the_list, substring):
    for i, s in enumerate(the_list):
        if substring in s:
            return i
    return -1

def string_match():
    test_list=['foo bar abc xml','fdff gdnfgf gdkgf','foo bar','abc','xml','xyz']
    max_len=4 # I am storing the maximum length of sentence
    # the list starts with reverse order
    # i.e sentence with highest length are at the top
    safe_to_add=[]
    for s in test_list:
        if len(s)==max_len:
            safe_to_add.append(s)
        else:
            idx=index_containing_substring(safe_to_add,s)
            if idx==-1:
                safe_to_add.append(s)
            else:
                # process the substring
                print('match found <{}> for <{}>'.format(test_list[idx],s))

This method works fine but I think it is pretty slow. Is there a better way to solve this problem using a better data structure (trie or suffix tree)?

Output

match found <foo bar abc xml> for <foo bar>
match found <foo bar abc xml> for <abc>
match found <foo bar abc xml> for <xml>

Answer 1

This is one of those times when "the rubber meets the road" as far as big-O complexity goes. You've got n = 2.5e6 words, so all that stuff about how \$O(\log n) < O(n) < O(n\log n) < O(n^2)\$ starts to be important.

Existing performance

You'll want to get a meaningful set of sample data, maybe 10 or 100 thousand words, and you'll want to look at using the timeit module, or something else you devise, to measure real performance.

That said, let's look at your code:

def index_containing_substring(the_list, substring):
    for i, s in enumerate(the_list):
        if substring in s:
            return i
    return -1

This function is called with a single word from the input list of words. It checks that one word against all the words already present in the_list. To do that, it iterates over the_list once, and then uses the in operator on each value.

Eventually, the_list is going to be sized based on the input word list. If nearly every word in the input list is a substring of some larger word, for example: [ 'aaaa', 'aaa', 'aa', 'a' ] then you will have one member. But if every word in the input is distinct, for example: [ 'a', 'b', 'c', 'd' ] you will have len(the_list) == N where N is the number of input words. For the worst case, we have to assume this.

For the use of substring in s, Python's substr in string is worst-case \$O(s \cdot t)\$, according to this post. In this analysis, s and t are lengths of the string and substring. Since your substrings eventually get added to the list, s == t. Thus, your index_containing_substring is worst-case \$O(n \cdot s^2)\$ (and average case about \$O(n \cdot s)\$).

def string_match():
    test_list=[...]
    safe_to_add=[]

    for s in test_list:
        if len(s)==max_len:
            safe_to_add.append(s)
        else:
            idx=index_containing_substring(safe_to_add,s)
            if idx==-1:
                safe_to_add.append(s)
            else:
                ...

In this function, you iterate once over the entire list of strings, calling the index_containing_substring function for almost every one. Your behavior is worst-case \$O(n)\$ where n is the length of the word list, times the behavior of the index_containing_substring function, which is \$O(n \cdot s^2)\$. Thus, your overall performance is \$O(n^2 \cdot s^2)\$, which since \$n \gg s\$ simplifies to \$O(n^2)\$.

It's worth noting that there are some "constant factors" in there which get ignored. For example, every time through the loop you check the length of your inputs to determine if you can add them without checking if they are contained substrings. This is a mistake for two reasons: first, what if they are duplicates? I don't see you doing any quality checks on the data, so I can't guarantee that two copies of "the longest word in the list" don't appear, and get added twice. Second, of course, is that you say the words are sorted in reverse order by length. This means that doing the substring-check on the first, long words is the cheapest operation possible. Checking for substrings in a list of length 0, or 1, is much much cheaper than it will ever be again. So you aren't saving very much. But you are doing that length comparison every single time.

I'd suggest that you either (1) abandon all that stuff entirely, and just pay the small price for the first couple of words; or (2) create a separate loop at the beginning to filter those words into the list, and then run your main loop starting after those are done.

An alternative

Suppose you computed every substring of a word. That would require iterating across the entire word, and for each point you reached you would iterate across all possible lengths of the substring:

word, wor, wo, w
 ord, or, o
  rd, r
   d

That is going to be \$O(s^2)\$ where s is the length of your word.

Now suppose you added all of the generated substrings to a Python set that has \$O(1)\$ access time. You could do something like this:

for word in big_list:
    if word in set_of_all_substrings:
        ...
    else: 
        add_all_substrings_of(word, set_of_all_substrings)

Assuming your "found" condition is \$O(1)\$, the performance is \$O(n \cdot s^2)\$, which again simplifies to \$O(n)\$.

Another alternative

Suppose you build a table of suffixes of all the words. That is, word[i:] for i in range(len(word)). Adding a single word's suffixes would be \$O(s)\$ as you can see, instead of \$O(s^2)\$ for substrings.

You could then binary-search the list, comparing word < suffix[:len(word)] to test for membership. The binary search would be \$O(\log n)\$ and you would do it n times, so your overall performance would be \$O(n \log n)\$. This seems worse than the \$O(n)\$ above, but it might be worth checking. The log(2.5 million) is about 22, and if your words have an average length of 10 letters, the difference between \$s\$ and \$s^2\$ would be 10, putting the two techniques a factor of 2.2 apart in performance. That's the kind of difference that code being written in C versus Python, or being particularly well-tuned for a particular purpose, can overcome.

Note that I don't expect this to work: inserting values into a sorted list gets quite expensive, so I suspect you'll find that this code loses the battle of small performance tweaks. But that's why they run horse races, eh?