数据结构考研分类复习真题 第四章 串[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;

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