I'm attempting to implement strstr using the KMP method. This is the algorithm described on scaler topics; I also watched this video https://www.scaler.com/topics/data-structures/kmp-algorithm/ to learn more about it. The temporal complexity of the KMP algorithm is O(n), where n is the length of the bigger string.
The dominant step for constructing the partial match table is the character comparison between the pattern and the displaced pattern. This is executed m - 1 times where m is the length of K. Hence the algorithm is linearly dependent upon the size of K.
For the search part, the character comparison step again dominates. The number of times it is executed is determined by the rate at which sp and kp increase towards the string end. Since for a string S of length n there can be at most n shifts forward made either by the pattern or in the string, then at most 2n comparisons could be made. The search algorithm therefore has a linear performance of O(2n).
Hence the whole algorithm has a linear performance of O(m + 2n - 1). As 2n would usually be much greater than m, then the complexity is O(2n) which is O(n).
Also note that if K size > S size then K cannot possibly be found in S. Also, for there to be more than one instance of K in S then S size has to > K size. If K size = S size then there is only a possible one instance of K in S.
PS. Note that the posted code above has issues (signed/unsigned mismatch etc) and that S and K are passed by value rather than const ref (or std::string_view).