想问下数据结构KMP模式匹配算法的next[j]为什么是下面写的那样
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/06/25 20:46:20
想问下数据结构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
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]为什么是下面写的那样](/uploads/image/z/8453170-10-0.jpg?t=%E6%83%B3%E9%97%AE%E4%B8%8B%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84KMP%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95%E7%9A%84next%5Bj%5D%E4%B8%BA%E4%BB%80%E4%B9%88%E6%98%AF%E4%B8%8B%E9%9D%A2%E5%86%99%E7%9A%84%E9%82%A3%E6%A0%B7)
你的理解有点偏差,设模式串为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数组的算法多看几遍就可明白了.
再问: 你那是观察法,我讲得是另一种方法,我是想问另一种方法是什么东西相等加一
再答: 求next数组最简单就是这种方法了,又何来另一种方法? 由定义,next[1]肯定是0 设next[j]=k,就会有,(1
你看的是不是清华大学那本数据结构呢,有点说的不清不楚的.那个求next数组的算法多看几遍就可明白了.
再问: 你那是观察法,我讲得是另一种方法,我是想问另一种方法是什么东西相等加一
再答: 求next数组最简单就是这种方法了,又何来另一种方法? 由定义,next[1]肯定是0 设next[j]=k,就会有,(1
想问下数据结构KMP模式匹配算法的next[j]为什么是下面写的那样
串模式匹配的kmp算法中next[0]的值到底是0还是-1;next[1]的值又到底是1还是0?
求模式串acabbcacabd的KMP算法中NEXT[j],可用图表示.
写出模式acabbcacabd的KMP算法中next[j],用图表示
模式匹配KMP算法思想是理解的 但是对应的next分段函数 这是啥意思啊 这个函数的自变量和值 分别代表什么现实意义?
KMP算法,输三组主串S和模式串P,输出模式串的Next(j)函数值,及该P在S中的位置的定
KMP算法中next的求解方法
关于KMP算法求next值的问题
kmp算法求next[]值, 练习:求T=”AAAAAAAAAAB” 的模式函数值,并用后面的求模式函数值函数验证。
kmp算法中的next
KMP算法next函数?
KMP算法,next数组的值,不是很懂,就给个例子吧.请看下面的补充