The justification is similar to the argument that the number of iterations in KMPMatch is
O
(
n
).