Is it possible to find specified substrings in a string in one iteration or faster then O(n*m)?

user_14370531 0
Viewed 101

I have a string and list of unique substrings. The problem is to identify, which substrings occur in our string.

It can be done simply with 2 nested loops.

result = []
substrings = ['foo', 'bar', 'spam', 'eggs']
text = 'foo123123spameggsabcde'

for s in substrings:
    if s in text:
        result.append(s)

But it is slow, especially whith long string and many substrings. Is there a way to perform this more efficiently?

time-complexity optimization algorithm python performance
1 Answers

Using SomeDude's algorithm from this similar question, the following should work quite efficiently:

lens=set([len(i) for i in substrings])
d={}
for k in lens:
    d[k]=[text[i:i+k] for i in range(len(text)-k)]
s=set(sum(d.values(), []))
result=list(s.intersection(set(substrings)))

print(result)

['foo', 'spam', 'eggs']

Explanation: We saved all possible lengths of the words in substrings. For these lengths, we created all possible substrings in text (set s). Finally we found common items in s and substrings, which is the answer to the question.

user_82285580
Related