The key point is to calculate the "next" array. The above code is somewhat intricate and not easy to understand. Actually it uses the DP idea to calculate the next position (in the pattern) to compare, in which case the "next" position of a latter position depends on that of the previous one.