帮帮忙谢谢先 - C语言论坛

bcomer

等　级：新手上路
帖　子：113
专家分：0
注　册：2004-9-13

第 2 楼

得分:0

以下是引用knocker在2004-10-05 14:54:09的发言：

不知道有人看懂了没有？

我的意思是模式匹配,对字符串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编辑过]

2004-10-05 15:08

bcomer

等　级：新手上路
帖　子：113
专家分：0
注　册：2004-9-13

第 4 楼

得分:0

我写的有那么混乱吗，

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

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

帮忙给几个好的USL吧

谢谢先

2004-10-06 22:03

bcomer

等　级：新手上路
帖　子：113
专家分：0
注　册：2004-9-13

第 6 楼

得分:0

以下是引用神vLinux飘飘在2004-10-08 16:25:08的发言：

求NEXT数组的函数来源（http://cn.math.pku.edu.cn/teachers/zhangnx/ds/%C1%A2%CC%E5%BF%CE%BC%FE/PS/%C4%A3%CA%BD%C6%A5%C5%E4/%BC%C6%CB%E3next%CA%FD%D7%E9%B5%C4%D4%B4%B3%CC%D0%F2.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'）,一直到匹配成功为止。

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

没关系，谢谢！

Thank you!神vLinux飘飘!

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

2004-10-08 17:05