Question

In pattern searching problem (searching a string of length m in a text of length n where n >= m), if we know that all characters of the pattern to be searched are distinct, what are the minimum time and extra space requirements to search pattern

Answer 1

Explanation:

Considering worst case scenario,

Time complexity O(n) will be = (n-m) × (m)

O(n) = (n-m)×m

And additional Space required = m