數據結構考研分類復習真題 第四章 串[5]

　　．下列算法實現求采用順序結構存儲的串s和串t的一個最長公共子串 【上海大學 一 （分）】

　　程序（a）

　　PROCEDURE  maxcomstr(VAR st : orderstring; VAR indexlength : integer);
　　VAR ijklength:integer;  con:boolean;
　　BEGIN
　　index :=; length :=;  i :=;
　　WHILE(i<=slen) DO
　　[j:=;
　　WHILE (j<=tlen) DO
　　[ IF (s[i]=t[j])  THEN
　　[ k:=;  length:=;  con:=true;
　　WHILE  con  DO
　　IF ()__THEN [length:=length+;k:=k+;] ELSE() _;
　　IF (length>length) THEN [index:=i; length:=length; ]
　　()____;
　　]
　　ELSE ()____;
　　]
　　() ___;
　　]
　　END;

　　程序(b)

　　void  maxcomstr(orderstring *s*t; int index length)
　　{int ijklengthcon;
　　index=;length=;i=;
　　while (i<=slen)
　　{j=;
　　while(j<=tlen)
　　{ if (s[i]= =t[j])
　　{ k=;length=;con=;
　　while(con)
　　if () _ { length=length+;k=k+; }  else () __;
　　if (length>length) { index=i;  length=length; }
　　()____;
　　}
　　else () ___;
　　}
　　() __
　　}
　　}

　　．完善算法求KMP算法中next數組【中山大學 四 （分）】

　　PROC get _next(t:stringVAR next:ARRAY[tlen] OF integer);
　　BEGIN
　　j:=; k:=()__;  next[]:=;
　　WHILE j<tlen DO
　　IF k= OR tch[j]=tch[k] THEN BEGIN j:=j+; k:=k+; next[j]:=k;END
　　ELSE k:=()___;
　　END;

　　．下面函數index用於求t是否為s的子串若是返回t第一次出現在s中的序號(從開始計)否則返回【南京理工大學 三 （分）】

　　例如:s=abcdefcdekt=cde則indse(st)= index(saaa)= 已知ts的串長分別是mtms
　　FUNC index(stmsmt);
　　i:=;j:=;
　　WHILE  (i<ms) AND (j<mt) DO
　　IF s[i]=t[j] THEN  [ ()__; ()__]
　　ELSE [ ()___; ()_ ]
　　IF j>mt THEN  return ()____; ELSE  return ()__
　　ENDF;

[]  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22587.html