What is the complexity of the substring search algorithm in a string, and how is it calculated? Please explain. (the algorithm is damp but simplified as an example and for understanding)

text='bla-bla-this-bla' subtext='this' for i,element in enumerate(text): if element == subtext[0]: if subtext == text[i:i+len(subtext)]: print(i)

    1 answer 1

    Let be:

     n = len(text) m = len(subtext)

    Obviously, the for loop will do n iterations in the worst case, inside each iteration, in the worst case, we make a text[i:i+len(subtext)] , which is executed for O (m) , and then a comparison for the same O (m) , as a result we get O (nm).

    • m constant, it is discarded - Komdosh
    • @Komdosh well, not a fact, because a substring can be of comparable length with a string - Pavel Karateev
    • but we do not run along it in a cycle, only according to text - Komdosh
    • @Komdosh is not directly, but we are making a slice text[i:i+len(subtext)] , the complexity of which is just tied to the length of the substring, plus the comparison subtext == text[i:i+len(subtext)] not constant time is running. - Pavel Karateev
    • @Komdosh Then, in your opinion, and n is a constant :) After all, we take a specific string? :) - Harry