算法包括5个重要元素：

• 主串S，假定为字符数组
• 模式串P，假定为字符数组
• int next[]
• 主串索引?i?，从0开始
• 模式串索引?j ，从0开始

?next[j] ：P[0]~P[j-1] 组成的字符串，首尾依次匹配，得到的相同元素的个数，规定next[0] = -1

要点：

? ? 1.主串索引 i 在匹配过程中只增加，增加原因有两个：

• 与模式串对应位匹配OK，和 j 同时增加；
• 匹配不OK，且 next[j] 的值为 0 或 -1时，和 j同时增加；?

? ? ?2.模式串索引 j 在匹配过程中则有增减

• 匹配成功时和 i 同时增加；
• 减少是因为匹配失败，获取 j = next[j] 时变小；

? ? 3. j 为模式串中匹配的起点

欢迎评论发表意见，互相学习。?