数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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 ）。