With amortized analysis, can show that computing the prefix-function is O(m).
For more informaiton, see the book, pages 871-874.
