Give a justification of why the computeFailKMP method (Code Fragment 13.4) runs in O(m) time on a pattern of length m.

Transcribed Image Text:

1 private static int[] computeFailKMP(char[ ] pattern) { int m = pattern.length; int[ ] fail = new int[m]; int j = 1; 2 // by default, all overlaps are zero 3 4 int k = 0; while (j < m) { if (pattern[i] = faili] = k + 1; j++; k++; } else if (k > 0) k = fail[k-1]: else 5 // compute fail li] during this pass, if nonzero // k +1 characters match thus far pattern[k]) { 10 // k follows a matching prefix 11 12 // no match found starting at j 13 14 j++; } return fail; 15 16 17 }