Suffix search - Python

You can break this into two parts. First, finding the shortest substring that matches some property. We'll pretend we already have a function that tests for the property:

def find_shortest_ss(document, some_property):
    # First level of looping gradually increases substring length
    for x in range(len(document)):
        # Second level of looping tests current length at valid positions
        for y in range(max(len(document), len(document)-x)):
            if some_property(document[y:x+y]):
                return document[y:x+y]
    # How to handle the case of no match is undefined
    raise ValueError('No matching value found')

Now the property we want to test for itself:

def contains_all_terms(terms):
    return (lambda s: all(term in s for term in terms))

This lambda expression takes some terms and will return a function which, when evaluated on a string, returns true if and only if all the terms are in the string. This is basically a more terse version of a nested function definition which you could write like this:

def contains_all_terms(terms):
    def string_contains_them(s):
        return all(term in s for term in terms)
    return string_contains_them

So we're actually just returning the handle of the function we create dynamically inside of our contains_all_terms function

To piece this together we do like so:

>>> find_shortest_ss(document, contains_all_terms(searchTerms))
'program can google'

Some efficiency advantages which this code has:

1. The any builtin function has short-circuit evaluation, meaning that it will return False as soon as it finds a non-contained substring

2. It starts by checking all the shortest substrings, then proceeds to increase substring length one extra character length at a time. If it ever finds a satisfying substring it will exit and return that value. So you can guarantee the returned value will never be longer than necessary. It won't even be doing any operations on substrings longer than necessary.

3. 8 lines of code, not bad I think

Well, brute force is O(n³), so why not:

from itertools import product

def find_shortest(doc, terms):
    doc = document.split()
    substrings = (
        doc[i:j]
        for i, j in product(range(0, len(doc)), range(0, len(doc)))
        if all(search_term in doc[i:j] for search_term in search_terms)
    )
    shortest = doc
    for candidate in substrings:
        if len(candidate) < len(shortest):
            shortest = candidate
    return shortest.
document = 'many google employees can program can google employees because google is a technology company that writes program'
search_terms = ['google', 'program', 'can']

print find_shortest(document, search_terms)
>>>> ['program', 'can', 'google']

You can probably do this a lot faster, though. For example, any relevant substring can only end with one of the keywords

Instead of brute forcing all possible sub-strings, I brute forced all possible matching word positions... It should be a bit faster..

import numpy as np
from itertools import product


document = 'many google employees can program can google employees because google is a technology company that writes program'
searchTerms = ['google', 'program']

word_lists = []

for word in searchTerms: 
    word_positions = []
    start = 0  #starting index of str.find()
    while 1:
        start = document.find(word, start, -1)
        if start == -1:  #no more instances
            break
        word_positions.append([start, start+len(word)])  #beginning and ending index of search term
        start += 1  #increment starting search postion
    word_lists.append(word_positions)  #add all search term positions to list of all search terms

minLen = len(document)
lower = 0
upper = len(document)
for p in product(*word_lists):  #unpack word_lists into word_positions
    indexes = np.array(p).flatten()  #take all indices into flat list
    lowerI = np.min(indexes)
    upperI = np.max(indexes)
    indexRange = upperI - lowerI  #determine length of substring
    if indexRange < minLen: 
        minLen = indexRange
        lower = lowerI
        upper = upperI

print document[lower:upper]