目錄

4.串

4.1串的定義和實現

4.2串的模式匹配

部分習題

---

4.串

4.1串的定義和實現

?

?

?

?

?

?

??

4.2串的模式匹配

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

---

部分習題

1.設有兩個串S1和S2，求S2在S1中首次出現的位置的運算稱為（）

A.求字串? ? ? ? B.判斷是否相等? ? ? ? C.模式匹配? ? ? ? D.連接

2.串‘ababaaababaa’的next數組值為（）

A.01234567899? ? ? ? B.012121111212

C.011234223456? ? ? ? D.0123012322345

3.串‘ababaaababaa’的next數組為()

A.-1,0,1,2,3,4,5,6,7,8,8,8? ? ? ? B.-1,0,1,0,1,0,0,0,0,1,0,1

C.-1,0,0,1,2,3,1,1,2,3,4,5? ? ? ? D.-1,0,1,2,-1,0,1,2,1,1,2,3

4.串‘ababaaababaa’的nextval數組為()

A.010112010102? ? ? ? B.010114110102

C.010104210104? ? ? ? D.011102110104

5.主串T=‘abaabaabcabaabc’，模式串S=‘abaabc’,采用KMP算法模式匹配，到匹配成功為止，在匹配過程中進行的單個字符間的比較次數是（）

A.9? ? ? ? B.10? ? ? ? C.12? ? ? ? D.15

---

1.C

求字串是從串S中截取第i個字符起長度為l的字串，A錯誤

2.C

采用手工求next數組的方法，得

序號j	1	2	3	4	5	6	7	8	9	10	11	12
串	a	b	a	b	a	a	a	b	a	b	a	a
next[j]	0	1	1	2	3	4	2	2	3	4	5	6

故選C

3.C

next數組整體-1，故選C（在實際KMP算法中，為了簡潔，串的位序從1開始，則next數組要整體加1，若位序從0開始，則不加1）

4.C

采用手工求nextval數組方法，得

序號j	1	2	3	4	5	6	7	8	9	10	11	12
串	a	b	a	b	a	a	a	b	a	b	a	a
nextval[j]	0	1	0	1	0	4	2	1	0	1	0	4

故選C

5.B

next數組

序號j	1	2	3	4	5	6
串	a	b	a	a	b	c
next[j]	0	1	1	2	2	3

第一次匹配，連續比較6次，在6號位匹配失敗，下一次比較位置為next[3]，即從模式串的3號位與主串的6號位比較，第二次匹配4次，匹配成功，因此共匹配10次