想问下数据结构KMP模式匹配算法的next[j]为什么是下面写的那样j 1 2 3 4 5 6 7 8 模式串a b a a b c a cnext[j] 0 1 1 2 2 3 1 2以上是一一对应有解释说是相等加1,不相等向前找,首位置不等1,我理解是前一

想问下数据结构KMP模式匹配算法的next[j]为什么是下面写的那样j 1 2 3 4 5 6 7 8 模式串a b a a b c a cnext[j] 0 1 1 2 2 3 1 2以上是一一对应有解释说是相等加1,不相等向前找,首位置不等1,我理解是前一
想问下数据结构KMP模式匹配算法的next[j]为什么是下面写的那样
j 1 2 3 4 5 6 7 8
模式串a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
以上是一一对应
有解释说是相等加1,不相等向前找,首位置不等1,我理解是前一个位置和首位置比较相不相等,
如果是的话,为什么第5个位置的前一个位置不是和首位置一样吗?那不是应该加一吗?那不就是3

想问下数据结构KMP模式匹配算法的next[j]为什么是下面写的那样j 1 2 3 4 5 6 7 8 模式串a b a a b c a cnext[j] 0 1 1 2 2 3 1 2以上是一一对应有解释说是相等加1,不相等向前找,首位置不等1,我理解是前一
你的理解有点偏差,设模式串为string[i],求next[j]不是前面一个相等就加一,而是要看前面紧接的子串有多少个相等,j=4时紧接的子串只有string[3]==string[1],故next[j] =2,同理j=5时也只有string[4]==string[1],故next[j] =2.如果要next[5]=3,必须要满足string[3]==string[1]并且string[4]==string[2]的条件.
你看的是不是清华大学那本数据结构呢,有点说的不清不楚的.那个求next数组的算法多看几遍就可明白了.