ref

Overview

strStr() is a classic question in CS. There are various ways to solve (which we have discussed before), this is a summarization:

1. naive - O(m * n)

2. KMP - O(n) in worst case

3. Rabin-Karp, rolling hash - between O(m * n) and O(m + n)

   Matches the hash value of the pattern with the hash value of pattern. If the hash values match, then only it starts matching individual characters.

4. Modified naive algo, only work if pattern contains no duplicate characters.

   Only match the first char. This case is quite boring, can skip.

5. Suffix tree

   Will discuss in details.