第四章串
一、内容提要
1、是数据元素为字符的线性表，串的定义及操作。
2、串的基本操作，编制算法求串的其它操作。
3、串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小“的问题。静态和动态（块链结构，堆结构）存储的优缺点。
4、朴素模式匹配算法及改进（KMP）算法。
二、学习重点
1、串的基本操作，编写串的其他操作（如index,replace等）。
2、在串的模式匹配中，求匹配串的nextval 函数值。
3、尽管朴素的模式匹配的时间复杂度是O(m*n), KMP算法是O(m+n),但在一般情况下，前者实际执行时间近似O(m+n),因此至今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。
5、串操作在存储结构下的实现。
三、例题解析
1、利用串的如下基本运算
create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编写操作replace的算法
replace(string &s,string t, string v)
//本算法实现串的置换操作，用串v置换串s中所有非重叠的t串。
{i=INDEX(s,t);{判s中有无t}
IF (i!=0)
{CREATE (temp, ‘’);{t为临时串变量，存放部分结果}
m=LENGTH(t);n=LENGTH(s);
WHILE (i!=0)
{ ASSIGN (temp,CONCAT(temp,SUBSTR(s,1,i-1),v));
//用v替换t形成部分结果
ASSIGN (s,SUBSTR(s, i+m,n-i-m+1)); //t串以后形成新s串
n= n-(i-1)-m;
i=INDEX(s,t);
}
ASSIGN (s,CONCAT(temp,s)); //将剩余s连接临时串t再赋给s
}
}
int index(string s,string t)
//本算法求串t在串s中的第一次出现。结果是：若t在s中，则给出串t的第一个字符在串s中的位置，若不存在，则返回0
{j=1;m=length(s); n=length(t); eq=true;
WHILE((j<=m-n+1)&& eq )
IF equal(substr(s,j,n),t)
eq=false;
ELSEj=j+1；
IF( j<=m+n-1)return(j);
Return(0);
}
【讨论】本题是用给定的基本操作，编写其它操作的算法。这种类型题较多，必须严格按题的要求来做，不准选择具体存储结构。否则，即使全对，也很难得分。
2 设目标为t=’abcaabbabcabaacbacba’,模式串
p=’abcabaa’;
(1)计算P的NEXTVAL函数值；
(2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程；
【解答】
【讨论】为写NEXTVAL方便，可先写出NEXT函数值，在由此求NEXTVAL.
3、字符串s 满足下式，其中HEAD 和 TAIL的定义同广义表类似，如
HEAD(‘XYZ’)=’X’,TAIL(‘XYZ’)=’YZ’,则
S=concat(head(tail(s)),head(tail(tail(s))))=’dc’
求字符串s。
可供选择的答案是（A） abcd(B) acbd(C) acdb(D) adcb
正确答案是（D）。
四、基本题
（一）选择题
1．下面关于串的的叙述中，哪一个是不正确的？（）【北方交通大学 2001 一、5（2分）】
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
2若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,inde x(S2,‘8’),length(S2)))
其结果为（）【北方交通大学1999一、5（25/7分）】
A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345
E．ABC###G1234F．ABCD###1234G．ABC###01234
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）
A．求子串B．联接C．匹配D．求串长
【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】
4．已知串S=‘aaab’,其Next数组值为（）。【西安电子科技大学 1996 一、7 （2分）】
A．0123B．1123C．1231D．1211
5．串‘ababaaababaa’ 的next数组为（）。【中山大学 1999 一、7】
A．012345678999 B．012121111212C．011234223456D．0123012322345
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 )
【北京邮电大学 1999一、1（2分）】
7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。
