作业帮想问下数据结构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,我理解是前一
来源：学生作业帮助网 编辑：作业帮 时间：2024/10/04 06:18:50
![想问下数据结构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,我理解是前一](/uploads/image/z/13045844-20-4.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%B7j+1+2+3+4+5+6+7+8+%E6%A8%A1%E5%BC%8F%E4%B8%B2a+b+a+a+b+c+a+cnext%5Bj%5D+0+1+1+2+2+3+1+2%E4%BB%A5%E4%B8%8A%E6%98%AF%E4%B8%80%E4%B8%80%E5%AF%B9%E5%BA%94%E6%9C%89%E8%A7%A3%E9%87%8A%E8%AF%B4%E6%98%AF%E7%9B%B8%E7%AD%89%E5%8A%A01%2C%E4%B8%8D%E7%9B%B8%E7%AD%89%E5%90%91%E5%89%8D%E6%89%BE%2C%E9%A6%96%E4%BD%8D%E7%BD%AE%E4%B8%8D%E7%AD%891%2C%E6%88%91%E7%90%86%E8%A7%A3%E6%98%AF%E5%89%8D%E4%B8%80)
xRnPW*u QU,$̣PBB`C smJkWk9gfL NOV[ZfTR^_yKɏVAbJ.ZOpJ`m
L{E [kڻK
z^$EI=8\9 Y k%[;QujRY4GiTob_46I&%*nk%V86=kz
1=m8ٶ`['
q$+X;!c jܜ)0G/e7ծ9&m e #+pхWMS @+a 9` w{P"$[#w`*hp?~g?!y3ArĠ}g2n`f*aL.;qvD>i !%Y# XHm nD,~V᷋@h&ֿ o-JH"ς7}sx*9їXk>&rccmFq2cQ@*/
想问下数据结构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数组的算法多看几遍就可明白了.