构造next数组步骤
1.计算最长公共前缀后缀数组 next[]; //即最长的，前缀与后缀相同的长度。
2.将next中所有元素右移一位，第1个元素置为-1；
3.将next中所有元素加1。
算法运行：当第j个元素不匹配时，模式串右移j-next[j]个字符。 j从1开始
例如模式串：xyxyyxxyx
构造next数组：
步骤1：所得next={0,0,1,2,0,1,1,2,3}
步骤2： next={-1,0,0,1,2,0,1,1,2}
步骤3： next={ 0,1,1, 2,3,1,2,2,3}
原文：http://www.cnblogs.com/dan-cnblogs/p/4769388.html