算法包括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 为模式串中匹配的起点