四、应用题
1．名词解释：串 【大连海事 1996 一、10 (1分) 】【河海大学 1998 二、5（3分）】
2．描述以下概念的区别：空格串与空串。【大连海事大学 1996 三、2、（1） (2分)】
3．两个字符串s1和s2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为t(m,n)。估算最优的t(m,n)，并简要说明理由。 【北京工业大学 1996 一、5 (6分)】
4．设主串s=‘xxyxxxyxxxxyxyx’，模式串t=‘xxyxy’。请问：如何用最少的比较次数找到t在s中出现的位置？相应的比较次数是多少？ 【大连海事大学 2001 四 (8分)】
5．kmp算法(字符串匹配算法)较brute(朴素的字符串匹配)算法有哪些改进?【大连海事大学1996三、1((2分)】
6．已知模式串t=‘abcaabbabcab’写出用kmp法求得的每个字符对应的next和nextval函数值。
【北京邮电大学 1997 三 （10分）】
7．给出字符串‘abacabaaad’在kmp算法中的next和nextval数组。【北京邮电大学 2000 三、1（5分）】
8．令t=‘abcabaa’,求其next 函数值和nextval函数值。 【北方交通大学 1994 一 （6分）】
9．已知字符串‘cddcdececdea’，计算每个字符的next和nextval函数的值。【南京邮电大学 2000 一 2】
10．试利用kmp算法和改进算法分别求p1=‘abaabaa’和p2=‘aabbaab’的next函数和nextval函数。
【东南大学 1999 一、6（8分）】
11．已知kmp串匹配算法中子串为babababaa,写出next数组改进后的next数组信息值（要求写出数组下标起点）。【西南交通大学 2000 二、2】
12．求模式串t=‘abcaabbac’ 的失败函数next(j)值。【西安交通大学 1996 四、4 (5分)】
13．字符串的模式匹配kmp算法中,失败函数(next)是如何定义的?计算模式串p=‘aabaabaaabc’中各字符的失败函数值.【石油大学 1998 一、2 (10分)】
14．设字符串s=‘aabaabaabaac’，p=‘aabaac’
（1）给出s和p的next值和nextval值；
（2）若s作主串，p作模式串，试给出利用bf算法和kmp算法的匹配过程。
【北方交通大学1998二（15分）】
15．设目标为t=‘abcaabbabcabaacbacba’,模式为p=‘abcabaa’
（1）计算模式p的naxtval函数值；（5分）
（2）不写出算法,只画出利用kmp算法进行模式匹配时每一趟的匹配过程。（5分）
【清华大学 1998 八（10分）】
16．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的kmp算法的时间复杂性是多少？如果，某一模式 p=’abcaacabaca’，请给出它的next函数值及next函数的修正值nextval之值。【上海交通大学 2000 一 （5分）】
17．设目标为s=‘abcaabbcaaabababaabca’，模式为p=‘babab’，
（1）手工计算模式p的nextval数组的值；(5分)
（2）写出利用求得的nextval数组，按kmp算法对目标s进行模式匹配的过程。 (5分)
【清华大学 1997 四（10分）】
18．用无回溯的模式匹配法（kmp法）及快速的无回溯的模式匹配法求模式串t的next[j]值，添入下面表中：
j1 2 3 4 5 6 7
ta a b b a a b
kmp法求得的next[j]值
快速无回溯法求得的next[j]值
【北京邮电大学 1992 三、1（25/4分）】
责任编辑：小草
