数据�l�构�W�四章填�I�题�?qi��ng)参考答案[5]_跨考网

1�Q�完善算法：(x��)�?/span>KMP���法�?/span>next数组�?/span>

　　PROC get _next(t:string,VAR next:ARRAY[1..t.len] OF integer);

　　BEGIN

　　j:=1; k:=(1)__; next[1]:=0;

　　WHILE j<t.len DO

　　IF k=0 OR t.ch[j]=t.ch[k] THEN BEGIN j:=j+1; k:=k+1; next[j]:=k;END

　　ELSE k:=(2)___;

　　END;

　　�?a target="_blank">中山大学 1998 四�?/span>1 �Q?/span>4分）(j��)�?/span>

 (t��ng) (t��ng) (t��ng) 【参考答案�?/span>

 (t��ng) (t��ng) (t��ng) �Q?/span>1�Q?/span>0 �Q?/span>2�Q?/span>next[k]

 (t��ng)

　　2�Q�下面函�?/span>index用于�?/span>t是否�?/span>s的子�Ԍ��若是�q�回t�W�一�ơ出现在s中的序号(�?/span>1开始计)�Q�否则返�?/span>0�?/span>

　　例如:s=�?/span>abcdefcdek’，t=�?/span>cde�?/span>,�?/span>indse(s,t)=3, index(s,�?/span>aaa�?/span>)=0 。已�?/span>t�Q?/span>s的串长分别是mt,ms

　　FUNC index(s,t,ms,mt);

　　i:=1;j:=1;

　　WHILE (i<ms) AND (j<mt) DO

　　IF s[i]=t[j] THEN [ (1)__; (2)__]

　　ELSE [ (3)___; (4)_ ]

　　IF j>mt THEN return (5)____; ELSE return (6)__

　　ENDF;

 (t��ng) (t��ng) (t��ng) �?a target="_blank">南京理工大学 1999 三�?/span>2 �Q?/span>6分）(j��)�?/span>

 (t��ng) (t��ng) (t��ng) 【参考答案�?/span>

 (t��ng) (t��ng) (t��ng) �Q?/span>1�Q?/span>i�Q?/span>=i+1 �Q?/span>2�Q?/span>j:=j+1 (3)i:=i-j+2 (4)j:=1; (5)i-mt�Q�或i:=i-j+1�Q?/span> (6)0