Thursday, November 7, 2013

KMP

Spent some time understanding how KMP works. The code is  from http://blog.csdn.net/v_july_v/article/details/7041827.

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.