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

A:O(n) time and O(1) extra space
B:O(n) time and O(m) extra space
C:O(n*m) time and O(m) extra space
D:O(m) time and O(m) extra space​

Answer 1

B) O(n) time and O(m) extra space is required for searching when string is having length m in a text of length n (n>=m).

Answer 2

This pattern searching problem takes minimum of O(n*m) time and O(m) extra space.

Explanation:

• here in the pattern searching algorithm two loops are used and one auxiliary array is used to store the comparing substrings from the text.
• first loop traverses through the string 'text' of length 'n' hence the time for this traversal is O(n).
• second loop is a nested loop inside the first loop that compares the string 'pattern' of length 'm' to the next 'm' character of string 'text' starting at the corresponding index determined from the first loop.
• hence, the combined traversal time is given by O(nm).
• now while performing the comparison an array of size same as that of 'pattern' is maintained to store the compared characters to keep the track of the matching. Hence, extra space required is O(m)