How to calc the next array.
Calc the max length of suffix and prefix as follows:
string a b a a b c a b a length 0 0 1 1 2 0 1 2 3 next -1 0 0 1 1 2 0 1 2 As you can see, the next array is the suffix equals prefix length array move on one step and init the first values as -1.
1 | void GetNext(char* p,int next[]) |