数据�l�构�W�四章填�I�题及参考答案[4]_跨考网

　1�Q�下列算法实现求采用��序�l�构存储的串s和串t的一个最长公共子丌Ӏ?/span>

　　�E�序�Q?/span>a�Q?/span>

　　PROCEDURE maxcomstr(VAR s,t : orderstring; VAR index,length : integer);

　　VAR i,j,k,length1:integer; con:boolean;

　　BEGIN

　　index :=0; length :=0; i :=1;

　　WHILE(i<=s.len) DO

　　[j:=1;

　　WHILE (j<=t.len) DO

　　[ IF (s[i]=t[j]) THEN

　　[ k:=1; length1:=1; con:=true;

　　WHILE con DO

　　IF (1)__THEN [length1:=length1+1;k:=k+1;] ELSE(2) _;

　　IF (length1>length) THEN [index:=i; length:=length1; ]

　　(3)____;

　　]

　　ELSE (4)____;

　　]

　　(5) ___;

　　]

　　END;

　　�E�序(b)

　　void maxcomstr(orderstring *s,*t; int index, length)

　　{int i,j,k,length1,con;

　　index=0;length=0;i=1;

　　while (i<=s.len)

　　{j=1;

while(j<=t.len)

{ if (s[i]= =t[j])

　　{ k=1;length1=1;con=1;

　　while(con)

　　if (1) _ { length1=length1+1;k=k+1; } else (2) __;

　　if (length1>length) { index=i; length=length1; }

　　(3)____;

　　}

　　else (4) ___;

　　}

　　(5) __

　　} }�?a target="_blank">上�v大学 2000 一�?/span>2 �Q?/span>10分）�?/span>

    【参考答案�?/span>

    本题���法采用��序存储�l�构求串s和串t的最大公共子丌Ӏ�串s�?/span>i指针�Q?/span>1<=i<=s.len�Q��?/span>t串用j指针�Q?/span>1<=j<=t.len�Q�。算法思想是对每个i�Q?/span>1<=i<=s.len�Q�即�E�序中第一�?/span>WHILE循环�Q�，来求�?/span>i开始的�q�箋字符串与�?/span>j�Q?/span>1<=j<=t.len�Q�即�E�序中第二个�Q?/span>HILE循环�Q�开始的�q�箋字符串的最大匹配。程序中�W�三个（��x��内层�Q�的WHILE循环�Q�是�?/span>s中某字符�Q?/span>s�Q?/span>i�Q�）�?/span>t中某字符�Q?/span>t�Q?/span>j�Q�）相等�Ӟ��求出局部公共子丌Ӏ�若该子串长度大于已求出的最长公共子�Ԍ��初始为０�Q�，则最长公共子串的长度要修攏V�?/span>

    �E�序�Q?/span>a�Q�：�Q?/span>1�Q�（i+k<=s.len�Q?/span>AND(j+k<=t.len) AND(s[i+k]=t[j+k])  

                   //如果�?/span>s�?/span>t的长度内�Q�对应字�W�相�{�，则指�?/span>k 后移�Q�加1�Q��?/span> 

              �Q?/span>2�Q?/span>con:=false //s�?/span>t对应字符不等时置标记退�?/span>

              �Q?/span>3�Q?/span>j:=j+k //�?/span>t串中�Q�从�W?/span>j+k字符再与s[i]比较

              �Q?/span>4�Q?/span>j:=j+1 //t串取下一字符

              �Q?/span>5�Q?/span>i�Q?/span>=i+1 //s串指�?/span>i后移�Q�加1�Q��?/span>

    �E�序�Q?/span>a�Q�：�Q?/span>1�Q?/span>i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] //所有注释同�Q?/span>a�Q?/span>

              �Q?/span>2�Q?/span>con=0 (3) j+=k (4) j++ (5) i