第四章 串
第一部分：知识点
一、串的概念
由零个或多个字符组成的有限序列，一般记作
S = ‘a1a2a3...an’ （n0）
其中 S----串名， a1a2a3...an ----串值，ai可以是字母、数字或其他字符，
n----串长，当n=0时S是空串
串中任意连续的字符组成的子序列称为该串的子串。
主串：包含子串的串。
位置：字符在序列中的序号为该字符在串中的位置。
子串在主串中的位置则用子串的第一个字符在主串中的位置来表示。
例：s=“ababcabcac” , t=“abc” 子串t 在主串s中的位置为3
串相等：当两个串长度相同，并且各个对应位置的字符都相等时称两个串相等。
二、串的表示
串在计算机内有三种表示方式（1）定长顺序存储表示（2）堆分配存储表示（3）块链存储表示
1、串的定长顺序存储表示
#define MAXSTRLEN 255
// 用户可在255以内定义最大串长
typedef unsigned char Sstring[MAXSTRLEN + 1];
串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断” 。按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。
2、串的堆分配存储表示
typedef struct {
char *ch;
// 若是非空串，则按串长分配存储区，
// 否则ch为NULL
int length; // 串长度
} HString;
系统利用函数malloc( )和free( )进行串值空间的动态管理，为每一个新产
生的串分配一个存储区，称串值共享的存储空间为“堆”。
这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。
3、串的块链存储表示
串的链式存储结构称为链串，链串的组织形式与一般的链表类似。“节点大小”：由于串结构的特殊性，结点中的每个数据元素是一个字符，则用链表存储串值时，即每个结点可以存放一个字符，也可以存放多个字符，如图4.1所示。
图4.1 串的链式存储示意图
三、串的模式匹配算法
模式匹配：子串的定位操作。此时将子串又称为模式串。即下面操作：Index (S, T, pos)：从主串s 的第pos个字符开始查找子串(模式串）t第一次出现的位置。
1、简单匹配算法
算法的基本思想是：从主串s的第pos个字符起和模式串t的第一个字符比较之，若相等，则继续逐个比较后续字符，否则从主串s的下一个字符起再重新和模式t的字符比较之。依此类推，直至模式t中的每个字符依次和主串s中的一个连续的字符序列相等，则称匹配成功，函数值为和模式串中第一个字符相等的字符在主串s中的序号．否则称匹配不成功，函数值为0。
例：s=‘ababcabcacbab’ t = ‘abcac’ pos=1 ，匹配过程如下：
该算法最坏情况下T(n) = O(m*n)
2.改进的模式匹配算法—KMP算法
该算法消除了主串指针的回溯，当匹配过程中产生“失配”(即
s i≠tj)时，主串指针i不动，而是利用得到的部分匹配的结果，将模式串“向右滑动”尽可能远的距离，设此时j的位置是next[j]，然后继续从此位置进行匹配，显然算法的时间复杂度是O(m+n)。
a b c *
a b c a c
算法的关键就是next[j]的计算，研究后得出next[j]的值只与模式串有关。
关键是从匹配过的子串中找匹配的最长前缀子串和后缀子串(相互重叠的最大真子串) ,next[j]就是长度值+1.
例如：
j 1 2 3 4 5 j 1 2 3 4 5 6 7 8
模式串 a b c a c 模式串 a b a a b c a c
next[j] 0 1 1 1 2 next[j] 0 1 1 2 2 3 1 2
串匹配过程：
i=1,j=1
先由模式串计算next值。
比较s[i]和t[j],如果对应相等，则继续向后匹配i++,j++，一旦失配，更新j=next[j];
当j=0时，i++,j++;然后重复以上操作直到串t扫描完毕，匹配成功，或串s扫描完毕，匹配失败。
发现，用上述方法计算出的next[j]，有时并不是模式串向右滑动的最大距离。
例如下面这种特殊情况：
S = aaabaaabaaabaaabaaab
T = aaaab
next[j]= 0 1 2 3 4
当j=4时失配：
i=4
aaa b aaabaaabaaabaaab
aaa a b
j=4
此时next[4]=3,调整j=3，模式串向右滑动一位,发现调整后仍然失
配，需要再根据next函数，调整j值，如此直到j=0，原因失配时t j值与
t next[j]相同。
设next[j]=k，若T[j]==T[k]则：修正next[j]= next[k]
用nextval[j]表示next[j]的修正值，则有：
k=next[j]= nextval[j] T[j]≠ T[k]
nextval[j]=
nextval[k] 否则
例如计算nextval值
j 1 2 3 4 5
T = a a a a b
nextval[j]= 0 0 0 0 4
第二部分：习题
一、选择题
1．下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以
采用链式存储
2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,
执行
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ）。
A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345
E．ABC###G1234 F．ABCD###1234 G．ABC###01234
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算
法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
4．已知串S=‘aaab’,其Next数组值为（ ）。
A．0123 B．1123 C．1231 D．1211
5．串 ‘ababaaababaa’ 的next数组为（ ）。
A．012345678999 B．012121111212 C．011234223456 D．0123012322345
