文件名称：KMP主算法-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:12
数据结构 邓俊辉
代码11.3 KMP主算法 11.3.4 next[0] = -1 空串是任何非空串的真子串、真前缀和真后缀，故只要j > 0则必有0 N(P, j)。此 时N(P, j)必非空，从而保证“在其中取最大值”这一操作的确可行。但反过来，若j = 0， 则前缀prefix(P, j)本身就是空串，它没有真子串，于是必有集合N(P, j) = 。 此种情况下，又该如何定义next[0]呢？ 表11.3 next表实例：假惱地附加一个通配符P[-1] rank -1 0 1 2 3 4 5 6 7 8 9 P[] * C H I N C H I L L A next[] N/A -1 0 0 0 0 1 2 3 0 0 按照串匹配算法的构思，若某轮迭代中首对字符即失配，则应将模式串P直接右移一个 字符，然后从其首字符起继续下一轮比对。 就实际效果而言，这一处理方法完全等价于“令next[0] = -1”。如表11.3所示，不 妨假想地在P[0]的左侧“附加”一个P[-1]，而且该字符与任何字符都是匹配的。 11.3.5 next[j + 1] 那么，若已知next[0, j]，如何才能递推地计算出next[j + 1]？是否有高效方法？ 图11.7 P[j] = P[next[j]]时，必有next[j + 1] = next[j] + 1 若next[j] = t，则意味着在前缀prefix(P, j)中，自匹配的真前缀和真后缀的最大 长度为t，故必有next[j + 1] next[j] + 1而且特别地，当且仅当P[j] = P[t] 时如图11.7取等号。那么一般地，若P[j] P[t]，又该如何得到next[j + 1]？