KMP中next数组的理解

next数组是KMP的核心，但对于next数组我们总是有时候感觉明白了，但有时候又感觉没明白，现在我就说下我自己对KMP中next数组的理解，首先next[i]上的数字的意义，next[i]表示的是当匹配到匹配串的第i个字母适配的时候，改跳到的位置，为什么要跳，是因为不想回到0重新浪费时间去比较，在深一点理解，我感觉next[i]，里存的是 找两个相同的尽量长的字符串，一个是以从匹配串的第一个字母开始的，另一个是以失配字母i的前一个点结尾的，他俩可以有相交的地方，但不能完全相交，得到这两个串的最大长度后+1，就是next[i],通俗的理解就是假如

1231231234 当匹配到4的时候突然失配了，那么我们就找两个串，以个是以第一个开头，另一个是以4前面的那个3结尾，可以相交但不可以完全相交，得到的就是123123 123123，那么当4失配的时候就直接跳到第二个3后后面的那个1比较就行了，因为当前的这个失配点的前一个点为尾的串和以第一个点为起点的串的相等关系，我们可以有把握的直接跳，减少时间。总之next,KMP给我的感觉就是记忆化搜索，而记忆化搜索我有觉得是DP，所以KMP感觉也是dp吧。毕竟是每一步都不会去走多余的路。