NEXT数组:

有点不明白

举个例子:

P="ABCAABABC"

i= 0 1 2 3 4 5 6 7 8

Pi= A B C A A B A B C

K 0 0 0 1 1 2 1 2

比较 != != = != = != = =

next[i] -1 0 0 -1 0 0 2 0 0

我认为next[0]=-1;

if(是=号) next[i]=next[k]-1;

else next[i]=next[k];

是吗?可NEXT[8]=0而不是1;

麻烦给讲讲可以吗?

不知道有人看懂了没有？

我的意思是模式匹配,对字符串T=t1t2...tn;P=p1p2...pm;1<m<=n;

在T中查找和P相同的字符串的一种无回溯算法;

其中用到了NEXT数组,

想知到NEXT数组应该如何计算?

我看到的书中提到了以下的方法

先考虑K

K表示p0p1....pn中最大的前后缀长度

再比较pk和pi查看是否相等

最后得出NEXT数组

不知道说明白了没有

谁能给讲讲,我在计算时总是和实际(在1-2个数上)有所不同

[此贴子已经被作者于2004-10-05 15:10:34编辑过]

请喝茶！帮忙看看先

[em45]

有点晕！

我写的有那么混乱吗，

ai,我的意思是，我想看看NEXT数组的解释（NEXT数组是数据结构模式匹配部分的）

和计算方法，我觉得我明白的，但和答案有少许不同

帮忙给几个好的USL吧

谢谢先

求NEXT数组的函数 来源（http://cn.math.pku.edu.cn/teachers/zhangnx/ds/Á¢Ìå¿Î¼þ/PS/ģʽƥÅä/¼ÆËãnextÊý×éµÄÔ´³ÌÐò.htm）

void makeNext(PSeqString p, int *next)

/* 变量next是数组next的第一个元素next[0]的地址 */

{ int i=0,k=-1; /* 初始化 */

next[0]=-1; while (i<p->n-1) /* 计算next[i+1] */ { while (k>=0 && p->c[i]!=p->c[k]) { k=next[k]; /* 找出p0…pi中最大的相同的前后缀长度k */ }

i++; k++;

if (p->c[i]==p->c[k]) /* 填写next[i]，同时考虑改善 */ next[i]=next[k];

else next[i]=k; }

}

计算next数组最简单的方法就是穷举法，算法的复杂度为O(m*m)，整个算法的复杂度为O(m*m+n)。 不过还有复杂度为O(m)的算法，思想如下：假设P1P2...Pk = Pi-k+1...Pi，那么next[i] = k + 1 。当我们计算next[i+1]时，如果发现Pk+1 = Pi+1, 也就是P1P2...PkPk+1 = Pi-k+1...PiPi+1，那么next[i+1] = next[i] + 1 = k + 2。 但是如果Pk+1 <> Pi+1, 则比较next[k]和Pi+1（找下一个满足P1P2...Pk' = Pi-k'+1...Pi的k'）,一直到匹配成功为止。

真是对不起，我还没看完数据结构，我也是现炒现卖的，真的对不起了

[此贴子已经被作者于2004-10-08 16:26:07编辑过]

没关系，谢谢！

Thank you!神vLinux飘飘!

[此贴子已经被神vLinux飘飘于2004-10-08 17:16:42编辑过]