数据结构 | 每日一练（111）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．在改进了的（无回溯）字符串模式匹配中，要先求 next 数组的值。下面是求 nextval 值的算法。

TYPE SAR=ARRAY[1..m] OF INTEGER;

PTY=ARRAY[1..m] OF CHAR;

PROCEDURE next2(P:PTY;VAR NEXTVAL:SAR);

{在模式 P 中求 nextval 数组的值}

1 1 BEGIN

2 2 J:=1;NEXTVAL[1]:=0;K:=0

3 3 REPEAT

4 4 IF (K=0) OR (P[J]=P[K])

5 5 THEN [ J:=J+1;K:=K+1;

6 6 IF P[J]=P[K]

7 7 THEN NEXTVAL[J]:=NEXTVAL[K]

8 8 ELSE NEXTVAL[J]:=K ]

9 9 ELSE K:=NEXTVAL[K]

10 10 UNTIL J=m

11 11 END;

算法中第 4 行有 P[J]=P[K],第六行中也有 P[J]=P[K]。两处比较语句相同。请分析说明此两处比较语句的含义是什么？分析此算法在最坏情况下的时间复杂度是多少？

正确答案

PS：||代表注释

1．第4行的p[J]=p[K]语句是测试模式串的第J个字符是否等于第K个字符，如是，则指针J和K均增加1，继续比较。第6行的p[J]=p[K]语句的意义是，当第J个字符在模式匹配中失配时，若第K个字符和第J个字符不等，则下个与主串匹配的字符是第K个字符；否则，若第K个字符和第J个字符相等，则下个与主串匹配的字符是第K个字符失配时的下一个（即NEXTVAL[K]）。该算法在最坏情况下的时间复杂度O（m 2 ）。