Beginning Java Data Structures and Algorithms

Rationalization of the Naive Search Algorithm

The naive search algorithm takes O((n - m + 1)m) time, which is a tight bound on the worst case. We can imagine a worst case of the naive search algorithm if we have a text string with the character a repeating for n times, that is, an (such as a5 = "aaaaa"), and the pattern am (for m <= n). In this case, we have to execute the inner loop m times to validate the shift.

The naive search algorithm can be improved if we know that all characters in pattern P are different. In this case, whenever we fail validating a shift because P[j] doesn't match T[i + j], we don't need to backtrack. Instead, we can start validating the next shift on (i + j), therefore reducing the running time of the algorithm ...