第四章串

壹、選擇題

1.下面有關(guān)用的的論述中，哪壹種是不封的的？（）【北方交通大孥壹、5（2分）】

A.串是字符的有限序列B.空串是由空格構(gòu)成的事

C.模式匹配是串的壹種重要運(yùn)算D.串既可以采用次序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)

2若串S尸'ABCDEFG',S2='9898',S3='###',S4=‘012345,，執(zhí)行

concat(replace(SI,substr(Sl,length(S2),length(S3)),S3),substr(S4,index(S2,*81),length(S2)))

其成果卷(）【北方交通大學(xué)1999壹、5（25/7分）】

A.ABC###G0123B.ABCD###2345C.ABC###G2345D.ABC###2345

E.ABC###G1234F.ABCD###1224G.ABCa##01234

3.設(shè)有兩fl司串P和q，其中q是P的子串,求q在P中初次出琪的位置的算法稱(chēng)懸（）

A.求子串B.聯(lián)接C.匹配D.求串是

【北京郵甯大阜二、4（20/8分）】【西安甯子科技大學(xué)1996壹、1（2分）】

4.已知串S='aaab',其N(xiāo)ext數(shù)組值卷（）?！疚靼仓刈涌萍即髮W(xué)1996登、7（2分）】

A.0123B.1123C.1231D.1211

5.串'ababaaababaa'的next數(shù)組卷（【中山大學(xué)1999受、7】

A.B.C.D.5

6.字符串'ababaabab'的nextval（）

A.(0,1,0,1,04,1,0,1)B.(0,1,0,1,0,2,1,0,1)

C.(0,1,0,1,0,0,0,1,1)D.(0,1,0,1,0,1,0,1,1)

【北京郵甯大學(xué)1999壹、1（2分）】

7.模式串t="abcaabbcabcaabdab,,該模式串的next數(shù)組的值懸（)?nextval數(shù)組的值^()o

A.01112211123456712B.01112121123456112

C.01110013101100701D.01112231123456712

E.01100111011001701F.0110213101102701

t北京郵重大阜19983(2分)】

8.若串S='software',其子串的數(shù)目是（）?！疚靼插缸涌萍即箧蹜?yīng)用宜、2（2分）】

A.8B.37C.26D.9

9.設(shè)S卷壹種是度卷n的字符串，其中的字符各不相似，則S中的互異的非平凡子串（非空且不登樣于S

自身）的值I數(shù)卷（)。【中科院計(jì)算所1997]

A.2n-lB.n2C.(n2/2)+(n/2)D.(n2/2)+(n/2)-1E.(n2/2)-(n/2)-1F.其他狀況

10.串的房:度是指（）【北京工商大孥壹、6(3分)】

A.串中所含不壹樣字母的俯I數(shù)B.串中所含字符的保I數(shù)

C.串中所含不壹樣字符的偃I數(shù)D.串中所含非空格字符的他數(shù)

二、判斷題

1.KMF算法的特黠是在模式匹配畤指示主串的指針不曾變小。（〉【北京郵甯大摯壹、4（1分）】

2.設(shè)模式串的畏度卷m,目的串的晨度卷n,常n和m且處理只匹配堂次的模式畤，樸素的匹配（即子串定

位函數(shù)）算法所花的疇間代價(jià)也言午畬更卷節(jié)省。（）【房沙鐵道學(xué)院1998壹、1（1分）】

3.串是壹種數(shù)據(jù)量寸象和操作都特殊的線性表。（）【大連海事大孥1、L（1分）】

二、填空題

1.空格串是指（D,其畏度等于（2）?！疚靼插缸涌萍即髶窜浖?、4（2分）】

2.構(gòu)成串的數(shù)據(jù)元素只能是_______?！局猩酱蟾?998壹、5（1分）】

3.壹種字符串中_______稱(chēng)卷該串的子串?！救A中理工大學(xué)宜、3（1分）】

4.INDEX（'DATASTRUCTURE','STR'）=________。【福州大學(xué)1998二、4（2分）】

5.設(shè)正文串晨度卷n,模式串晨度懸m,則串匹配的KMP算法的畤間復(fù)雜度懸_______?

【重慶大學(xué)登、4】

6.模式串P='abaabcac'的next函數(shù)值序列懸_______?！疚靼插缸涌萍即蟾奋浖?、6（2分）】

7.字符串'ababaaab'的nextval函數(shù)值卷。【北京郵充大孥二、4（2分）】

8.設(shè)T和P是兩他各合定的串，在T中尋找等于P的子串的謾程稱(chēng)四，又稱(chēng)P焉⑵。

【西安甯子科技大學(xué)1998二、5(16/6分)】

9.串是有種特殊的線性表，其特殊性表目前(1):串的兩種最基木的存儲(chǔ)方式是(2)、(3)；

兩他串相等的充足必要條件是」k?！局袊?guó)礦業(yè)大孥壹、3(4分)】

10.兩值1字符串相等的充足必要條件是______。【西安花子科技大孽1999軟件壹、1(2分)】

11.知U=*xyxyxyxxyxy*：t=，xxy，；

ASSIGN(S,U)；

ASSIGN(V,SUBSTR(S,INDEX(s,t),LEN(t)+1))：

ASSIGN(m,'ww')

求REPLACE(S,V,m)=________?【柬北大阜1997登、1(5分)】

12.實(shí)現(xiàn)字符串拷貝的函數(shù)strcpy^：

voidstrcpy(char*s,char*t)/*copyttos*/

{while(________)

}【浙江無(wú)孥1999壹、5(3分)】

13.下列程序判斷字符串s與否封稱(chēng)，封稱(chēng)則返回1,否則返回0：如f("abba")返回1,f("abab")返回0：

intf(GJ)

{inti=0,j=0;

while(s[.j])(2);

for(j-;i<j&&s[i]==s[j];i++,j-);

return((3))

}【浙江大學(xué)1999壹、6(3分)】

14.下列算法實(shí)現(xiàn)求采用次序構(gòu)造存儲(chǔ)的串s和串t的登種最男公共子串。

程序(a)

PROCEDUREmaxcomstr(V?\Rs,t:orderstring;VARindex,length:integer);

VARi,j,k,lengthl:integer;con:boolean;

BEGIN

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

WHILE(i<=s.len)DO

[j：=l；

WHILE(j<=t.len)DO

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

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

WHILEconDO

IF￡1)THEN[lengthl:=lengthl+l;k:=k+l;]ELSE②;

IF(lcngthl>lcngth)THEN[indcx:=i;lcnglh:=lengthl;]

(3);

]

ELSE(4);

]

(5);

]

END;

程序(b)

voidmaxcomstr(orderstring*s,*t;intindex,length)

{inti,j,k,lengthI,con;

index=0;length=0;i=l;

whi1e(i<=s.len)

{j=l；

while(j<=t.len)

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

{k=l;lengthL=I;con=l;

while(con)

if(1){lengthl=lengthl+l;k=k+l：}else(2);

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

(3);

)

elseX4)；

}

(5)

}}【上海大暈宣、2：10分)】

15.完善算法：求KMP算法中next數(shù)組。

PROCget_next(t:string,VARnext:ARRAY[1..t.len]OFinteger);

BEGIN

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

WHILEj<t.lenDO

IFk=0ORt.ch[j]=t.ch[k]THENBEGINj:=j+l;k:=k+l;next[j]:=k;END

ELSEk:=(2);

END;

【中山大孥1998四、1(4分靖

16.下面函數(shù)index用于求t與否的子串，若是返回t第壹次出目前s中的序號(hào)(優(yōu)1始計(jì))，否則

返回0。

例如：s='abcdefcdek',t='cd?',則indse(s,t)=3,index(s,*aaa*)=0。已知t,s的呂縣分別

是mt,ms

FINCindex(s,t,ms,mt);

i：=l；j：=l；

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

IFs[i]=t[j]THEN[⑴；(2)_]

ELSE[13)_;]

IFj>mtTHENreturn⑨____:ELSEreturn?

ENDF;

【南京理工大孥1999三、2(5分)】

17.閱^下列程序闡明和pascal程序，把應(yīng)填入其中的()處的字句寫(xiě)在答題跋上。

程序闡明：

本程序用于鑒別輸入的字符串與否卷如下形式的字符串：

W&.MS其中，子字符串M是子字符串W的字符反向排列，在此假定W不具有字符&和字符$,字符&用作

“'與M的分隔符，字符$用作字符串的輸入束符。

例如，量寸輸入字符串a(chǎn)b&ba$、ab&dd$、&$，程序?qū)⒎謩e輸出0k.(是)，No.(不是)。

程序

PROGRAMaccept(input,output);

CONSTmidch=,&';endch=,$';

VARan:boolcan;ch:char;

PROCEDUREmatch(V.ARanswer:boolean);

VARchi,ch2:char;f:boolean;

BEGIN

read(chi);

IFchlOendch

THENIF￡1)

THENBEGINmatch(f);

IFfTHENBEGINread(ch2);answer.⑵ENDELSEanswer:=false

END

ELSE13)

ELSE(4)

END;

BEGIN

writeln(iEnterString:,);

match(an);

IFanTHENBEGIN

(5)IF(6)THENwriteln('Ok.')ELSEwriteln('No.')

END

ELSEwriteln('No.')

END.【上海海運(yùn)學(xué)院1998七（15分）】

18.試運(yùn)用下列棧和串的基本操作完畢下述填空題。

iritstack(s)置s懸空棧：

push(s,x)元素x入棧；

pcp(s)出棧操作；

gettop(s)返回棧頂元素；

sempty(s)判?？蘸瘮?shù)：

setnull(st)置串st懸空串；

length(st)返回串st的畏度；

ccual(si,s2)判串si和s2與否相等的函數(shù);

ccncat(si,s2)返回聯(lián)接si和s2之彳炎的串；

sub(s,i,1)返回s中第i他字符：

empty(st)判串空函數(shù)

FINCinvert（pre:string;VARexp:string）:boolean;

｛若,給定的體現(xiàn)式的前綴式pre封的，本迪!程求得和它封應(yīng)的體猊式exp并返回“true"，否則exp

卷空串，并返回“false”。已知原體所1式中不包括括弧，0Pset卷運(yùn)算符的集合。｝

VARs:stack：i,n:integer;succ:boolean;ch:char;

BEGIN

i:=1;n:=length(pre);succ:=true;

(1)；⑵；

WHILE(i<n)ANDsuccDO

BEGINch:=sub(pre,i,1)；

IF(3)THEN(4)_

ELSEIF15)THEN

ELSEBEGIN

exp:=concat((7)(8));

cxp:=concat((9)(10));

⑴)；

END;

i:=i+l

END;

IF(12)THEN

BEGINexp:=concat(exp.sub(pre,n,1));invert:=trueEND

ELSEBEGINsetnul1(exp);invert:=falseEND

END;

注意：每值I空格只填壹種^句?！厩迦A大學(xué)1996A]

四、應(yīng)用題

1.名同解釋?zhuān)捍敬筮B海事1996壹、10（1分）】【河海大孥1998二、5（3分）】

2.描述如下概念的區(qū)別：空格串與空串?！敬筮B海事大學(xué)1996三、2、（1）（2分）】

3.兩伍字符串S1和S2的是度分別卷m和n。求追兩催1字符串最大共同子串算法的畤間復(fù)雜度卷T（m,n）。

估和最優(yōu)的TGn,n）,并簡(jiǎn)要闡明理由?！颈本┕I(yè)大孥1996豈、5（6分）】

4.設(shè)主串S="xxyxxxyxxxxyxyx,,模式串T='xxyxy'。^惜J：怎樣用至少的比較次數(shù)找到T在S中出現(xiàn)

的位置？封應(yīng)的比較次數(shù)是多少？【大連海事大孥四（8分）】

5.KVP免法（字符串匹配算法）較Brute（樸素的字符串匹配）算法有哪些改善？【大連海事大學(xué)1996三、1（（2

分）】

6.已知模式串t='abcaabbabcab'寫(xiě)出用KMP法求得的每字符封應(yīng)的next和nextval函數(shù)值。

【北京郵花大學(xué)1997三（10分）】

7.^出字符串'abacabaaad'在KMP算法中的next和nextval數(shù)組?！颈本┼]甯大孥三、1（5分）】

8.令t='abcabaa',求其next函數(shù)值和nextval函數(shù)值。【北方交通大學(xué)1994壹（6分）】

9.已知字符串<cddcdececdca\計(jì)算每他字符的ncxI和ncxlval函數(shù)的值?！灸暇┼]霜大挈壹2】

10.試運(yùn)用KMP算法和改善第法分別求pl='abaabaa'和p2='aabbaab'的next函數(shù)和nextva.函數(shù)。

【束南大學(xué)1999壹、6（8分）】

11.已知KMP串匹配算法中子串卷babababaa,寫(xiě)出next數(shù)組改善彳爰的next數(shù)組信息值（規(guī)定寫(xiě)巴數(shù)組下

襟起黠）?！疚髂辖煌ù蟾范?、2]

12.求模式串丁=<abcaabbac，的失敗函數(shù)Ncxl（j）值。【西安交通大孥1996四、4（5分）】

13.字符串的模式匹配KMP和法中，失敗函數(shù)（NEXT）是怎樣定義的？計(jì)算模式串p='aabaabaaabc'中各字

符的失敗函數(shù)值.【石油大學(xué)1998登、2（10分）】

14.設(shè)字符串S=faabaabaabaac>?P=*aabaac,

（I）給出S和P的next值和nextval值；

（2）若S作主串，P作模式串，試^出運(yùn)用BF算法和KMP算法的匹配遇程。

【北方交通大孥】998二（15分）】

15.設(shè)目的'abcaabbabcabaacbacba',模式卷p=*abcabaa,

（I）計(jì)算模式p的naxtval函數(shù)值：（5分）

（2）不寫(xiě)出算法，只畫(huà)出運(yùn)用KM〉算法選行模式匹配畤每登趟的匹配謾程。（5分）

【清華大孥1998八（10分）】

16.模式匹配算法是在主串中迅速尋找模式的壹種有效的措施，假如設(shè)主串的長(zhǎng)度卷m,模式的長(zhǎng)度懸n,

則在主串中尋找模式的KMP算法的貸間復(fù)雜性是多少？假如，某壹模式P='abcaacabaca',出它的

NEXT函數(shù)值及NEXT函數(shù)的修正值NEXTVAL之值。【上海交通大學(xué)壹（5分）】

17.設(shè)目的^S=*abcaabbcaaabababaabcaJ,模式^>P='babab',

（l）手工計(jì)算:模式P的nextval數(shù)組的值：（5分）

（2）寫(xiě)出運(yùn)用求得的nextval數(shù)組，按KVP算法封目的S選行模式匹配的謾程。（5分）

【清華大孥1997四（10分）】

18.用輾【可溯的模式匹配法（KMP法）及迅速的輾回溯的模式匹配法求模式串T的next[j]值，添入下面表

中：

j1234567

taabbaab

kmp法求得的next[j]值

迅速瓢1可溯法求得的值

【北京郵甯大學(xué)1992三、1（25/4分）】

19.在改善了的（瓢回溯）字符串模式匹配中，要先求next數(shù)組的值。下面是求nextval值的算法。

TYPESAR=ARRAY[1..m]OFINTEGER;

PTY=ARRAY[1..m]OFCHAR;

PROCEDUREnext2（P:PTY;VARNEXTVAL:SAR）;

（在模式P中求nextval數(shù)組的值｝

1BEGIN

2J:=1;NEXTVAL[1]:=O;K:=O

3REPEAT

4IF(K=0)OR(P[J]=P[K])

5THEN[J:=J+1;K:=KH;

6IFP[J]=P[K]

7THENNEXTVAL[J]:=NEXTVAL[K]

8ELSENEXTVAL[J]:=K]

9ELSEK:=NEXTVAL[K]

10UNTILJ=m

11END;

和法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]o兩處比較^句相似。分析闡明此兩處比較聯(lián)普

句的含義是什么？分析此算法在最壤狀況下的H寺間復(fù)雜度是多少？【北京郵堂大孽1993二、2（6分）】

20.在字符串模式匹配的KMP算法中，求模式的next數(shù)組值的定義如下：

next[j]=

朋：

（D富j=l畤，卷何要取ncxl[l]=0?

（2）卷何要取max{K},K最大是多少？

（3）其他狀況是什么狀況，卷何取next[j]=l?【北京郵重大學(xué)1994二（8分）】

21.給出KMP算法中失敗函數(shù)f的定義，并闡明運(yùn)用f暹行串模式匹配的規(guī)則，該算法的技術(shù)特站是什么？

【束南大學(xué)1993受、3（9分）1997受、2（8分）壹、6（6分）】

22.在模試匹配KMP算法中所用失敗函數(shù)f的定義中,卷何規(guī)定PQ……p川南p.p2……pj兩^匹配的真

子串？且卷最大真子串？【柬南大孥1996壹、3（7分）】

23.假如兩假I(mǎi)串具有相等的字符，能否^它優(yōu)相等？【西安甯子科技大學(xué)軟件壹、3（5分）】

24.設(shè)S1,S2卷串，之青給出使S"/S2=S2〃S1成立的所有也的條件（〃卷連接符）。

【是沙鐵道阜院1997三、5（3分）】【國(guó)防科技大摯1999登】

25.已知：s='（xyz）+*',t='（x+z）*y'。試運(yùn)用聯(lián)結(jié)、求子串和置換等基本運(yùn)算，將s轉(zhuǎn)化

tO

【北方交通大孥1996壹、3（5分）】【山束科技大孥壹、6（5分）】

第五部分、算法設(shè)計(jì)

1.設(shè)s、t懸兩他1字符串，分別放在兩偃I壹維數(shù)組中，m、n分別懸其良度，判斷t與否懸s的子串。假如

是，輸出子串所在位置（第壹種字符），否則輸出0。（注：用程序?qū)崿F(xiàn)）【南京航空航天大學(xué)1997九（1（）

分）】

2.輸入壹種字符串，內(nèi)有數(shù)字和非數(shù)字字符，如：ak123x456I7960?302gef4563,將其中持續(xù)的數(shù)字作卷

壹種整體，依次寄存到壹數(shù)組a中，例如123放入a[0],456放入a[1],.....。編程記錄其共

有多少值I整數(shù)，并輸出道些數(shù)?！旧虾４蠹?998壹（13分）】

3.以次序存儲(chǔ)構(gòu)造表達(dá)半，設(shè)計(jì)算法。求串S中出現(xiàn)的第有種最旻反復(fù)子串及其位置并分析算法的畤問(wèn)

復(fù)雜度?！臼洗箧畚澹?5分）】

類(lèi)似本題的此外論述有:

（1）假如字符串的壹種子串（其是度不小于1）的各他1字符均相似，則稱(chēng)之卷等值子串。試設(shè)計(jì)壹算

法,輸入字符串S,以“！”作卷結(jié)束襟志。假如串S中不存在等值子串，則輸出信息“瓢等值子串”，否

則求出（輸出）受種畏度最大的等值子串。

例如:若S="abcl23abe123!”，則輸出“輾等值子串”：若S="abceebccadddddaaadd!”，則輸出“ddddd”。

【華中科技大孥1

4.假設(shè)串的存儲(chǔ)構(gòu)造如下所示，編寫(xiě)算法實(shí)現(xiàn)串的置換操作?！厩迦A大學(xué)1995五（15分）】

TYPEstrtp=RECORD

ch:ARRAY[1..maxlen]OFchar;

curlen:0..maxlen

END;

5.函數(shù)voidinsert（char*s,char*l,intpos）將字符串l插入到字符串s中，插入位置卷pos＜睛用c

^言實(shí)現(xiàn)該函數(shù)。假設(shè)分派給字符串s的空間足夠讓字符用t插入。（闡明：不得使用任何庫(kù)函數(shù)）

【北京航空航天大學(xué)六（10分）】

6.設(shè)計(jì)宣種二分檢索的郛法，在壹組字符串中找出^定的字符串，假設(shè)所有字符串的良度卷4。

（I）簡(jiǎn)述算法的重要思想：（3分）

（2）用PASCALS言分別封算法中用到的類(lèi)型和變量作出闡明：（3分）

（3）用類(lèi)PASCALS言或自然^言寫(xiě)算法的非遞歸遇程；（8分）

（4）分析該算法的最大檢索片度：（3分）

（5）必要處加上中文注釋。（3分）

【山柬工業(yè)大孥1995八（20分）】

7.設(shè)計(jì)壹PASCAL或CgS言的函數(shù)atoi（x）.其中X卷字符串，由0—9拾他數(shù)字符和表達(dá)正負(fù)數(shù)的構(gòu)成，

返回值卷整型數(shù)值?！菊憬髮W(xué)1994二（7分）】

8.已知字符串S1中寄存登段英文，寫(xiě)出算法format（sl,s2,s3,n）,將其按給定的是度n格式化成兩端封

齊的字符串S2,其多出的字符送S3。【首都自筌貿(mào)大孥1998三、8（15分）】

9.串以靜態(tài)存儲(chǔ)構(gòu)造存儲(chǔ)，構(gòu)造如下所述，試實(shí)現(xiàn)串操作equal算法.

CONSTmaxlen二串被確認(rèn)的最大是度

TYPEstrtp=RECORI）

ch:ARRAY[1..maxlen]OFchar;

curlen:0..maxlen

END;

（以豈維數(shù)組寄存串值，并設(shè)指示器curlen指示目前串艮）【北京輕工業(yè)大孥1998壹（12分）】

10.編寫(xiě)程序，記錄在輸入字符串中各（0不壹樣字符出現(xiàn)的頻度并珞成果存入文獻(xiàn)（字符串中的合法字符

卷A-Z追26他字母和0-9道10他數(shù)字）?！疚鞅贝箧鬯模?0分）】

11.寫(xiě)壹種遞歸算法來(lái)實(shí)垣字符串逆序存儲(chǔ)，規(guī)定不另設(shè)申存儲(chǔ)空間?！疚髂辖煌ù箧廴?、2]

12.已知三倜字符串分別懸s='ab…abcaabcbca…a',s'='caab',s''='bcb\運(yùn)用所摯字符串基

本運(yùn)算的函數(shù)得到成果串卷：s'"='caabcbca-aca-a,,規(guī)定寫(xiě)出得到上成果串S'''所用的函數(shù)及執(zhí)

行算法?！炯肀贝蠹?998壹、1（10分）】

13.S="S1S2…Sn”是壹種是卷N的字符串，寄存在壹種數(shù)組中，編程序?qū)改造之彳令輸出：

（1）將S的所有第偶數(shù)（0字符按照其本來(lái)的下襟優(yōu)大到小的次序放在S的彳灸半部分：

（2）將S的所有第奇數(shù)他字符按照其本來(lái)的下襟優(yōu)小到大的次序放在S的前半部分：

例如：

S=*ABCDEFGHIJK1/

則改造彳令的S卷'ACEGIKLJHFDB'。【中科院計(jì)算所1995]

14.編壹程序，封輸入的壹體現(xiàn)式（字符串），輸出其TOKEN表達(dá)。體現(xiàn)式由變量A,B,C,常數(shù)（數(shù)字）

0,1,…，9,運(yùn)算符+,*和括號(hào)構(gòu)成。首先定義符號(hào)的類(lèi)碼：

符號(hào)變量常量*+()

類(lèi)碼012345

另壹方面定義符號(hào)的TOKEN表達(dá):

其中NAMEL是變量名表（不容器午有相似名），CONST是常量表（不容器午有相似數(shù)）。

例如,假設(shè)有體現(xiàn)式（A+A*2）例*B*3#,則將生成如下TOKENL：

【吉林大阜1995壹(20分)】

第四章串

壹、選擇題

l.B2.E3.C4.A5.C6.A7.ID7.2F8.B注9.D10.B

注：子串的定義是：串中任意他持續(xù)的字符陶成的子序列，并規(guī)定空串是任意串的子串，任意串是

其自身的子串。若字符串晨度卷n(n>0),房卷n的子串有1f固，n-1的子串有2f固，房懸『2的子

串有3佛),……，1的子串有n(No由于空審是任何串的子串，因此木題的答案卷：8*(8+1)/2+1=37。

故選B。但某些教科害上認(rèn)卷“空串是任意串的子串”輾意義，因此認(rèn)卷選Co卷防止考試中的二道性，編

者認(rèn)卷第9題出得好。

二、判斷題

1.J2.J3.J

三.填空題

1.(1)由空格字符(ASCII值32)所構(gòu)成的字符串(2)空格值1數(shù)2.字符

3任意他1持續(xù)的字符構(gòu)成的子序

列4.55.0(m+n)

6.011223127.010104218.(1)模式匹配(2)模式串

9.(1)其數(shù)據(jù)元素都是字符(2)次序存儲(chǔ)(3)和鏈?zhǔn)酱鎯?chǔ)(4)串的良度相等且兩串中封應(yīng)位置的字符也相等

10.兩串的展度相等且兩串中量寸應(yīng)位置的字符也相等。

11.'xyxyxywwy>12.*s++=*l++或(*s++=*l++)!='\0'

13.(1)chars[](2)j++(3)i>=j

14.[題目分析]本題算法采用次序存儲(chǔ)構(gòu)造求串s和串t的最大公共子串。串s用i指針(l<=i〈=s.len)。

t串用j指針(l<="=t.len)o免法思想是封每他i(l<=i<=s.len,即程序中第言種WHILE循環(huán))，來(lái)

求優(yōu)i始的持續(xù)字符串與優(yōu)j(l<=j<=t.len,即程序中第二倜WEILE循環(huán))^始的持續(xù)字符串的最大匹

配。程序中第三他(即最內(nèi)層)的WHILE循環(huán)，是富s中某字符(s[i])與(中某字符(t[j])相等

畤，求出局部公共子串。若該子串是度不小于己求出的最畏公共子串(初始卷0),則最畏公共子串的房

度要修改。

程序(a)：(1)(i+k<=s.len)AND(j+k<=t.len)AND(s[i+k]=t[j+k])

〃假如在s和t的畏度內(nèi)，封應(yīng)字符相等，則指針k彳為移(加1)。

(2)con:=false//s和t封應(yīng)字符不等畤置襟識(shí)退出

(3)j:=j+k〃在t串中，優(yōu)第j+k字符再與s[i]比較

(4)j:=j+l//t串取F壹字符

(5)i：=i+l//s串指針i彳爰移(加1)c

程序(b)：(1)i+k<=s.len&&j+k<=t.len&&s(i+k]==t[j+k]〃所有注釋同上(a)

(2)con=0(3)j+=k(4)j++(5)i++

15.(1)0(2)next[k]

16.(1)i：=i+l(2)j:=j+l(3)i:=i-j+2(4)j:=l;(5)i-ml(或i:=i-」+l)(6)0

17.程序中遞歸調(diào)用

(1)chlOmidch〃富^入不是分隔符&和輸入結(jié)束符$畤，繼續(xù)^入字符

(2)chl=ch2〃^入分隔符&彳炎，判chi與否等于ch2,得出真假結(jié)論。

(3)answer：=true

(4)answer：=false

(5)read(ch)

(6)ch=endch

18.(1)initstack(s)//枚s初始化懸空棧。

(2)setnul1(exp)〃串exp初始化卷空串。

(3)chinopset〃判取出字符與否是操作符。

(4)push(s,ch)〃如ch是運(yùn)算符，則入運(yùn)算符棧

(5)sempty(s)〃判棧s與否卷空。

(6)succ:=false〃若^出ch是操作數(shù)且棧卷空，則按出籍處理。

(7)exp(8)ch〃若ch是操作數(shù)且棧非空，則形成部分口綴體現(xiàn)

式。

(9)exp(10)gettop(s)〃取棧頂操作符。

(11)pop(s)〃操作符取出彳笈，退棧。

(12)sempty(s)〃將pre的最終壹種字符(操作數(shù))加入到中綴式exp的最終。

四.應(yīng)用題

1.串是零他I至多種字符構(gòu)成的有限序列。優(yōu)數(shù)據(jù)構(gòu)造角度講，串屬于線性構(gòu)造。與線性表的特殊性在

于串的元素是字符。

2.空格是壹種字符，其ASCII碼值是32?？崭翊怯煽崭駱?gòu)成的串，其是度等于空格的他數(shù)。空串是

不含任何字符的串，即空串的是度是零。

3.最優(yōu)的T(m,n)是0(n)。串S2是串S1的子串，且在S1中的位置是1。I用始求出最大公共子串的

晨度恰是串S2的是度，壹般狀況下，T(m,n)=0(m*n)o

4.樸素的模式匹配(Brute-Force)疇間復(fù)雜度是O(m*n),KMP算法有壹定改善，疇間復(fù)雜度到

達(dá)0(m+n)o本題也可采用優(yōu)背面匹配的措施，即優(yōu)右向左掃描，比較6次成功。另壹種匹配方式是優(yōu)

左往右掃描，不遇先比較模式串的最終受種字符，若不等，則模式串彳為移；若相等，再比較模式圖的第壹

種字符，若第壹種字符也相等，則優(yōu)模式串的第二值1字符^始，向右比較，直至相等或失敗。若矢敗，模

式串彳為移，再反復(fù)以上謾程。按it種措施，本題比較18次成功。

5.KMP算法重要是處是主串指針不回溯。常主串很大不能壹次^入內(nèi)存且常常發(fā)生部分匹配畤，KMP

算法的是處更卷突出.

6.模式串的next函數(shù)定義如下:

next[j]=

根據(jù)此定義，可求解模式串t的next和nextval值如下:

j123456789101112

1串a(chǎn)bcaabbabcab

nexlfj]011122312345

nextval(j]011021301105

7.解法同上題6.其next和nextval值分別卷和010422.

8.解法同題6,t串的next和nextval函數(shù)值分別懸0111232和0110132。

9.解法同題6,其next和nextval值分別卷和01101301。

10.pl的next和ncxlval值分別卷：0112234和0102102；p2的ncxl和ncxlval值分別笊)：0121123和

0021002o

11.next數(shù)組值卷改善彳爰的next數(shù)組信息值卷。

12.o

13.next定義兄題上面6和下面題20。串p的next函數(shù)值卷：。

14.(1)S的nexl與nextval值分別卷和0000,p的next與nextval值分別卷012123和00。

(2)運(yùn)用BF算法的匹配迪!程:運(yùn)用KMP算法的匹配巡!程:

第直趟匹配：aabaabaabaac第壹趟匹配:aabaabaabaac

aabaac(i=6,j=6)

aabaac(i=6,j=6)

第二趟匹配：aabaabaabaac第二趟匹配:aabaabaabaac

aa(i=3,j=2)

(aa)baac

第三趟匹配：aabaabaabaac第三趟匹配:aabaabaabaac

a(i=3,j=l)(成功)

(aa)baac

第四趟匹配：aabaabaabaac

aabaac(i=9,j=6)

第五趟匹配：aabaabaabaac

aa(i=6,j=2)

第六趟匹配：aabaabaabaac

a(i=6,j=l)

第七趟匹配：aabaabaabaac

(成功)aabaac(i=13,j=7)

15.(Dp的nextval函數(shù)值卷0110132。(p的next函數(shù)值懸0111232)。

(2)運(yùn)用KMP(改善的nextval)算法，每趟匹配遇程如下:

第壹道匹配：abcaabbabcabaacbacba

abcab(i=5,j=5)

第二趟匹配：abcaabbabcabaacbacba

abc(i=7,j=3)

第三趟匹配：abcaabbabcabaacbacba

a(i=7,j=l)

第四趟匹配：abcaabbabcabaacbacba

(成功)abcabaa(i=15,j=8)

16.KMP算法的疇間復(fù)雜性是0(m+n)。

p的next和nextval值分別卷和0110220。

17.(I)p的nextval函數(shù)值卷01010。(next函數(shù)值卷01123)

(2)運(yùn)用所得nextval數(shù)值，手工模擬封s的匹配程，與上面16題類(lèi)似，懸節(jié)省篇幅，故略

去。

18.模式串T的next和nextval值分別卷0121123和0021002c

19.第4行的p[J]=p[K]1M句是測(cè)試模式串的第J值I字符與否等于第K值1字符，如是，則指針J和K均增

是1,繼續(xù)比較。第6行的p[J]=p[K]^句的意義是，富第J他1字符在模式匹配中失配畤，若第K佃字符和

第J偃I字符不等，則下他與主串匹配的字符是第K值|字符；否則，若第Kf固字符和第J他字符相等，則下

俯1與主串匹配的字符是第K保1字符失配畤的下宜種(即NEXTVAL[K])。

該算法在最摸狀況下的畤間旦雜度0(mJ。

20.(1)常模式串中第壹種字符與主串中某字符比較不等(失配)畤，next[l]