Suppose that all characters in the pattern \(P\) are different. Show how to accelerate NAIVE-STRING-MATCHER to run in time \(O(n)\) on an \(n\)-character text \(T\).

NAIVE-STRING-MATCHER-FOR-DISTINCT-PATTERN(T, P)

01 n = T.length

02 m = P.length

03 p_position = 0

04 for s = 0 to n - 1:

05      if T[s] == P[p_position]:

06          if p_position == m - 1:

07              print "Pattern occurs with shift" s - m + 1

08              p_position = 0

09          else:

10              p_position++

11      else:

12          p_position = 0

13          if T[s] == P[p_position]:

14              p_poisiton++;