DEV Community

loading...

Discussion on: The algorithm behind Ctrl + F.

Collapse
ylucet profile image
Yves Lucet

Agreed, but your article shows O(mn).

Thread Thread
akhilpokle profile image
Akhil Author

This algorithm works well if the alphabet is reasonably big, but not too big. If the last character usually fails to match, the current shift s is increased by m each time around the loop. The total number of character comparisons is typically about n/m, which compares well with the roughly n comparisons that would be performed in the naive algorithm for similar problems. In fact, the longer the pattern string, the faster the search! However, the worst-case run time is still O(nm). The algorithm as presented doesn't work very well if the alphabet is small, because even if the strings are randomly generated, the last occurrence of any given character is near the end of the string. This can be improved by using another heuristic for increasing the shift. Consider this example:

T = ...LIVID_MEMOIRS...
P = EDITED_MEMOIRS