What is the complexity of the algorithm for finding a substring in a string, and how is it calculated? Please explain. (the algorithm is crude, but simplified as an example and for understanding)
text='bla-bla-this-bla' subtext='this' for i,element in enumerate(text): if element == subtext: if subtext == text[i:i+len(subtext)]: print(i)
n = len(text) m = len(subtext)
It is obvious that the cycle
for make worst case
n iterations, in each iteration in the worst case we do slice
text[i:i+len(subtext)] , which is performed in O (m) , and then the comparison for the same O (m) , as a result we get O (nm).