KMP algorithm is an improved string matching algorithm proposed by D.E.Knuth, J.H.Morris and V.R.Pratt, so it is called Knut Morris Pratt operation (KMP algorithm for short). The core of KMP algorithm is to use the information after matching failure to reduce the matching times between pattern string and main string to achieve the purpose of fast matching. The specific implementation is realized by a next() function, which contains the local matching information of pattern string.
Now give you a text S, please output its next array.