when the pattern "does" occur in the text, running time of the original algorithm is in the worst case. this is easy to see when both pattern and text consist solely of the same repeated character. however, inclusion of the galil rule results in linear runtime across all cases.