Analysis of Compute-Good-Suffix-Function

COMPUTE-PREFIX-FUNCTION takes O(m) and two loops both of which are O(m). Therefore, COMPUTE-GOOD-SUFFIX-FUNCTION is O(m)


next up previous
Next: Analysis of Boyer-Moore Up: BOYER-MOORE Previous: Good-Suffix Heuristic Algorithm