第 4章 串
4.1 串类型的定义
4.2 串的表示和实现
4.3 串的模式匹配算法
4.1 串类型的定义串 是 由多个或零个字符组成的有限序列,记作
S = ‘c1c2c3…c n’ (n>=0)
其中,S是串名字,‘ c1c2c3…c n’是串值
ci是串中字符,n是串的 长度,表示串中字符的数目。
空串,零个字符的串称为空串 记作,?”
子串,串中任意个连续的字符组成的子序列主串,包含子串的串字符在串中的位置,字符在序列中的序号子串在串中的位置：子串的第一个字符在主串中的位置
串相等,p70
空格串,由一个或多个空格组成的串
串的表示,用一对单引号括起来
串的操作,以“串的整体”为操作对象
4.2 串的表示和实现
1.定长顺序存储表示
2.堆分配存储表示
3.串的块链存储表示
4.串的基本操作
1.定长顺序存储表示
静态分配
每个串预先分配一个固定长度的存储区域。
实际串长可在所分配的固定长度区域内变动
以下标为 0的数组分量存放串的实际长度；
在串值后加入” \0”表示结束，此时串长为隐含值
用定长数组描述：
#define MAXSTRLEN 255 //最大串长
typedef unsigned char SString[MAXSTRLEN + 1]
//0号单元存放串的长度
2.堆分配存储表示
以一组地址连续的存储单元存放串值字符序列；
存储空间动态分配，用 malloc()和 free()来管理
typedef struct
{char *ch;
int length;
}Hstring;
3.串的块链存储表示
串的链式存储方式
结点大小：一个或多个字符
P78图 4.2 (a) (b)
存储密度 =串值所占的存储位 /实际分配的存储位
4.串的基本操作
串插入 Status StrInsert(HString &S,int pos,HString T)
串赋值 Status StrAssign(HString &S,char *chars)
求串长 int StrLength(HString S)
串比较 int StrCompare(HString S,HString T)
串联接 Status Concat(HString &S,HString
S1,HString S2)
求子串 Status SubString(HString &Sub,HString S,int
pos,int len)
串清空 Status ClearString(HString &S)
串定位
删除
置换
Status StrInsert(HString &S,int pos,HString T)
//在串 S的第 pos个位置前插入串 T
{ int i;
if (pos<1||pos>S.length+1) return ERROR;
if (T.length){
if (!(S.ch=(char*)
realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit(OVERFLOW);
for (i=S.length-1;i>=pos-1;--i){
S.ch[i+T.length]=S.ch[i];
}
for (i=0; i<=T.length-1;i++)
S.ch[pos-1+i]=T.ch[i];
S.length+=T.length;
} return OK;
}
Status StrAssign(HString &S,char *chars)
生成一个值等于 chars的串 S
{ int i,j; char *c;
for (i=0,c=chars;*c;++i,++c);
if (!i) {S.ch=NULL; S.length=0;}
else {
if (!(S.ch=(char *)malloc(i * sizeof(char))))
exit(OVERFLOW);
for (j=0;j<=i-1;j++){
S.ch[j]=chars[j];}
S.length=i;
}
return OK;
}
int StrLength(HString S)
求串的长度
{
return S.length;
}
int StrCompare(HString S,HString T)
比较两个串，若相等返回 0
{
int i;
for (i=0;i<S.length && i<T.length; ++i)
if (S.ch[i] != T.ch[i]) return S.ch[i]-T.ch[i];
return S.length-T.length;
}
Status Concat(HString &S,HString S1,HString S2)
用 S返回由 S1和 S2联接而成的新串
{ int j;
if (!(S.ch =
(char*)malloc((S1.length+S2.length)*sizeof(char))))
exit(OVERFLOW);
for (j=0;j<=S1.length-1;j++){ S.ch[j]=S1.ch[j];}
S.length=S1.length+S2.length;
for (j=0;j<=S2.length-1;j++){
S.ch[S1.length+j]=S2.ch[j];}
return OK;
}
Status SubString(HString &Sub,HString S,int pos,int len)
用 Sub返回串 S的第 pos个字符开始长度为 len的子串
{
if (pos<1 || pos>S.length || len<0 ||len>S.length-pos+1)
return ERROR;
if (!len) { Sub.ch=NULL; Sub.length=0;}
else {
Sub.ch=(char *)malloc(len*sizeof(char));
for (int j=0;j<=len-1;j++){
Sub.ch[j]=S.ch[pos-1+j];}
Sub.length=len;
}
return OK;
}
Status ClearString(HString &S)
将 S清为空串
{
if (S.ch) { free(S.ch); S.ch=NULL;}
S.length=0;
return OK;
}
4.3 串的模式匹配算法
定义 在串中寻找子串（第一个字符）在串中的位置
词汇 在模式匹配中，子串称为模式,串称为 目标 。
示例 目标 S,,Beijing”
模式 P,,jin”
匹配结果 = 4
1.穷举模式匹配
设 S=s1,s2,…,sn( 主串 )P=p1,p2,…,pm(
模式串 )
i为指向 S中字符的指针,j为指向 P中字符的指针
匹配失败,si≠pj时，
(si-j+1 … s i-1)=(p1 … p j-1)
回溯,i=i-j+2 ; j=1
重复回溯太多,O(m*n)
第 1趟 S a b b a b a 穷举的模 式
P a b a 匹配过程第 2趟 S a b b a b a
P a b a
第 3趟 S a b b a b a
P a b a
第 4趟 S a b b a b a
P a b a
求子串位置的定位函数
int Index(SString S,SString T,int pos) {
//穷举的模式匹配
int i=pos; int j=1;
while (i<=S[0] && j<=T[0]) {//当两串未检测完,S[0],S[0]为串长
if (S[i]==T[j]) {++i; ++j;}
else {i=i-j+2; j=1;}
}
if (j>T[0]) return i-T[0]; //匹配成功
else return 0;
}
2.KMP快速模式匹配
D.E.Knuth,J.H.Morris,V.R.Pratt同时发现
无回溯的模式匹配
S s1 … si-j-1 si-j si-j+1 si-j+2 … si-1 si si+1 … sn
‖ ‖ ‖ ‖?
P p1 p2 … pj-1 pj pj+1 … p m
则有 si-j+1 si-j+2 … si-1 = p1 p2 … pj-1 (1)
为使模式 P 与目标 S 匹配，必须满足
p1 p2 … pj-1 pj… pm = si-j+1 si-j+2 … si-1 si … si-j+m
如果 p1 … pj-2? p2 p3 … pj-1 (2)
由 (1)(2)则立刻可以断定
p1 … pj-2? si-j+2 si-j+3 … si-1
下一趟必不匹配同样，若 p1 p2 … pj-3? p3 p4 … pj-1
则再下一趟也不匹配，因为有
p1 … pj-3? si-j+3 … si-1
直到对于某一个,k”值，使得
p1 … pk? pj-k pi-k+1… pj-1
且 p1 … pk-1 = pj-k+1 pj-k+2 … pj-1
则 p1 … pk-1 = si-k+1 si-k+2 … si-1
‖ ‖ ‖
pj-k+1 pj-k+3 … pj-1
模式右滑 j-k位
next数组值
假设当模式中第 j个字符与主串中相应字符“失配”时，可以拿第 k个字符来继续比较，则令 next[j]=k
next函数定义：
0 当 j=1时
next[j]= Max{k| 1<k<j 且’ p1…p k-1?=
pj-k+1…p j-1?}当此集合不空时
1 其他情况手工求 next数组的方法
序号 j 1 2 3 4 5 6 7 8
模式 P a b a a b c a c
k 1 1 2 2 3 1 2
Pk==Pj ≠ = ≠ = ≠ = ≠
next[j] 0 1 1 2 2 3 1 2
Nextval[j] 0 1 0 2 1 3 0 2
运用 KMP算法的匹配过程第 1趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
next(2) = 1
第 2趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c next(1)=0
第 3趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
next(6) = 3
第 4趟 目标 a c a b a a b a a b c a c a a b c
模式 (a b) a a b c a c
KMP算法
int Index_KMP(SString S,SString T,int
*next){ int i,j;
i=1; j=1;
while (i<=S[0] && j<=T[0]){
if (j==0 || S[i]==T[j]){++i;++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
}
求 next数组的步骤
(1)next[1]=0
i=1; j=0;
(2)设 next[i]=j
若 j=0,next[i+1]=1
若 Pi=Pj,next[i+1]=j+1=next[i]+1
若 Pi ≠ Pj,next[i+1]=next[j]+1
参看教材 p82~83递推过程求 next数组的函数
void get_next(SString S,int *next){
int i,j;
i=1; next[1]=0; j=0;
while (i<S[0]) {
if (j==0 || S[i]==S[j]) {++i; ++j;
next[i]=j;}
else j=next[j];
}
}
改进的求 next数组方法
设 next[i]=j
若 P[i]=P[j],则 nextval[i]=nextval[j]
改进的求 next数组的函数
void get_nextval(SString S,int *nextval){
int i,j;
i=1; nextval[1]=0; j=0;
while (i<S[0]) {
if (j==0 ||S[i]==S[j]){
++i;++j;
if (S[i]!=S[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}
穷举的模式匹配算法时间代价：
最坏情况比较 n-m+1趟，每 趟比较 m次，
总比较次数达 (n-m+1)*m
原因在于 每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。
改进的模式匹配 (KMP)算法的时间代价：
若每趟第一个不匹配，比较 n-m+1趟,总比较次数最坏达 (n-m)+m = n
若每趟第 m个不匹配，总比较次数最坏亦达到 n
求 next函数的比较次数为 m,所以总的时间复杂度是 O(n+m)
4.1 串类型的定义
4.2 串的表示和实现
4.3 串的模式匹配算法
4.1 串类型的定义串 是 由多个或零个字符组成的有限序列,记作
S = ‘c1c2c3…c n’ (n>=0)
其中,S是串名字,‘ c1c2c3…c n’是串值
ci是串中字符,n是串的 长度,表示串中字符的数目。
空串,零个字符的串称为空串 记作,?”
子串,串中任意个连续的字符组成的子序列主串,包含子串的串字符在串中的位置,字符在序列中的序号子串在串中的位置：子串的第一个字符在主串中的位置
串相等,p70
空格串,由一个或多个空格组成的串
串的表示,用一对单引号括起来
串的操作,以“串的整体”为操作对象
4.2 串的表示和实现
1.定长顺序存储表示
2.堆分配存储表示
3.串的块链存储表示
4.串的基本操作
1.定长顺序存储表示
静态分配
每个串预先分配一个固定长度的存储区域。
实际串长可在所分配的固定长度区域内变动
以下标为 0的数组分量存放串的实际长度；
在串值后加入” \0”表示结束，此时串长为隐含值
用定长数组描述：
#define MAXSTRLEN 255 //最大串长
typedef unsigned char SString[MAXSTRLEN + 1]
//0号单元存放串的长度
2.堆分配存储表示
以一组地址连续的存储单元存放串值字符序列；
存储空间动态分配，用 malloc()和 free()来管理
typedef struct
{char *ch;
int length;
}Hstring;
3.串的块链存储表示
串的链式存储方式
结点大小：一个或多个字符
P78图 4.2 (a) (b)
存储密度 =串值所占的存储位 /实际分配的存储位
4.串的基本操作
串插入 Status StrInsert(HString &S,int pos,HString T)
串赋值 Status StrAssign(HString &S,char *chars)
求串长 int StrLength(HString S)
串比较 int StrCompare(HString S,HString T)
串联接 Status Concat(HString &S,HString
S1,HString S2)
求子串 Status SubString(HString &Sub,HString S,int
pos,int len)
串清空 Status ClearString(HString &S)
串定位
删除
置换
Status StrInsert(HString &S,int pos,HString T)
//在串 S的第 pos个位置前插入串 T
{ int i;
if (pos<1||pos>S.length+1) return ERROR;
if (T.length){
if (!(S.ch=(char*)
realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit(OVERFLOW);
for (i=S.length-1;i>=pos-1;--i){
S.ch[i+T.length]=S.ch[i];
}
for (i=0; i<=T.length-1;i++)
S.ch[pos-1+i]=T.ch[i];
S.length+=T.length;
} return OK;
}
Status StrAssign(HString &S,char *chars)
生成一个值等于 chars的串 S
{ int i,j; char *c;
for (i=0,c=chars;*c;++i,++c);
if (!i) {S.ch=NULL; S.length=0;}
else {
if (!(S.ch=(char *)malloc(i * sizeof(char))))
exit(OVERFLOW);
for (j=0;j<=i-1;j++){
S.ch[j]=chars[j];}
S.length=i;
}
return OK;
}
int StrLength(HString S)
求串的长度
{
return S.length;
}
int StrCompare(HString S,HString T)
比较两个串，若相等返回 0
{
int i;
for (i=0;i<S.length && i<T.length; ++i)
if (S.ch[i] != T.ch[i]) return S.ch[i]-T.ch[i];
return S.length-T.length;
}
Status Concat(HString &S,HString S1,HString S2)
用 S返回由 S1和 S2联接而成的新串
{ int j;
if (!(S.ch =
(char*)malloc((S1.length+S2.length)*sizeof(char))))
exit(OVERFLOW);
for (j=0;j<=S1.length-1;j++){ S.ch[j]=S1.ch[j];}
S.length=S1.length+S2.length;
for (j=0;j<=S2.length-1;j++){
S.ch[S1.length+j]=S2.ch[j];}
return OK;
}
Status SubString(HString &Sub,HString S,int pos,int len)
用 Sub返回串 S的第 pos个字符开始长度为 len的子串
{
if (pos<1 || pos>S.length || len<0 ||len>S.length-pos+1)
return ERROR;
if (!len) { Sub.ch=NULL; Sub.length=0;}
else {
Sub.ch=(char *)malloc(len*sizeof(char));
for (int j=0;j<=len-1;j++){
Sub.ch[j]=S.ch[pos-1+j];}
Sub.length=len;
}
return OK;
}
Status ClearString(HString &S)
将 S清为空串
{
if (S.ch) { free(S.ch); S.ch=NULL;}
S.length=0;
return OK;
}
4.3 串的模式匹配算法
定义 在串中寻找子串（第一个字符）在串中的位置
词汇 在模式匹配中，子串称为模式,串称为 目标 。
示例 目标 S,,Beijing”
模式 P,,jin”
匹配结果 = 4
1.穷举模式匹配
设 S=s1,s2,…,sn( 主串 )P=p1,p2,…,pm(
模式串 )
i为指向 S中字符的指针,j为指向 P中字符的指针
匹配失败,si≠pj时，
(si-j+1 … s i-1)=(p1 … p j-1)
回溯,i=i-j+2 ; j=1
重复回溯太多,O(m*n)
第 1趟 S a b b a b a 穷举的模 式
P a b a 匹配过程第 2趟 S a b b a b a
P a b a
第 3趟 S a b b a b a
P a b a
第 4趟 S a b b a b a
P a b a
求子串位置的定位函数
int Index(SString S,SString T,int pos) {
//穷举的模式匹配
int i=pos; int j=1;
while (i<=S[0] && j<=T[0]) {//当两串未检测完,S[0],S[0]为串长
if (S[i]==T[j]) {++i; ++j;}
else {i=i-j+2; j=1;}
}
if (j>T[0]) return i-T[0]; //匹配成功
else return 0;
}
2.KMP快速模式匹配
D.E.Knuth,J.H.Morris,V.R.Pratt同时发现
无回溯的模式匹配
S s1 … si-j-1 si-j si-j+1 si-j+2 … si-1 si si+1 … sn
‖ ‖ ‖ ‖?
P p1 p2 … pj-1 pj pj+1 … p m
则有 si-j+1 si-j+2 … si-1 = p1 p2 … pj-1 (1)
为使模式 P 与目标 S 匹配，必须满足
p1 p2 … pj-1 pj… pm = si-j+1 si-j+2 … si-1 si … si-j+m
如果 p1 … pj-2? p2 p3 … pj-1 (2)
由 (1)(2)则立刻可以断定
p1 … pj-2? si-j+2 si-j+3 … si-1
下一趟必不匹配同样，若 p1 p2 … pj-3? p3 p4 … pj-1
则再下一趟也不匹配，因为有
p1 … pj-3? si-j+3 … si-1
直到对于某一个,k”值，使得
p1 … pk? pj-k pi-k+1… pj-1
且 p1 … pk-1 = pj-k+1 pj-k+2 … pj-1
则 p1 … pk-1 = si-k+1 si-k+2 … si-1
‖ ‖ ‖
pj-k+1 pj-k+3 … pj-1
模式右滑 j-k位
next数组值
假设当模式中第 j个字符与主串中相应字符“失配”时，可以拿第 k个字符来继续比较，则令 next[j]=k
next函数定义：
0 当 j=1时
next[j]= Max{k| 1<k<j 且’ p1…p k-1?=
pj-k+1…p j-1?}当此集合不空时
1 其他情况手工求 next数组的方法
序号 j 1 2 3 4 5 6 7 8
模式 P a b a a b c a c
k 1 1 2 2 3 1 2
Pk==Pj ≠ = ≠ = ≠ = ≠
next[j] 0 1 1 2 2 3 1 2
Nextval[j] 0 1 0 2 1 3 0 2
运用 KMP算法的匹配过程第 1趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
next(2) = 1
第 2趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c next(1)=0
第 3趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
next(6) = 3
第 4趟 目标 a c a b a a b a a b c a c a a b c
模式 (a b) a a b c a c
KMP算法
int Index_KMP(SString S,SString T,int
*next){ int i,j;
i=1; j=1;
while (i<=S[0] && j<=T[0]){
if (j==0 || S[i]==T[j]){++i;++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
}
求 next数组的步骤
(1)next[1]=0
i=1; j=0;
(2)设 next[i]=j
若 j=0,next[i+1]=1
若 Pi=Pj,next[i+1]=j+1=next[i]+1
若 Pi ≠ Pj,next[i+1]=next[j]+1
参看教材 p82~83递推过程求 next数组的函数
void get_next(SString S,int *next){
int i,j;
i=1; next[1]=0; j=0;
while (i<S[0]) {
if (j==0 || S[i]==S[j]) {++i; ++j;
next[i]=j;}
else j=next[j];
}
}
改进的求 next数组方法
设 next[i]=j
若 P[i]=P[j],则 nextval[i]=nextval[j]
改进的求 next数组的函数
void get_nextval(SString S,int *nextval){
int i,j;
i=1; nextval[1]=0; j=0;
while (i<S[0]) {
if (j==0 ||S[i]==S[j]){
++i;++j;
if (S[i]!=S[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}
穷举的模式匹配算法时间代价：
最坏情况比较 n-m+1趟，每 趟比较 m次，
总比较次数达 (n-m+1)*m
原因在于 每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。
改进的模式匹配 (KMP)算法的时间代价：
若每趟第一个不匹配，比较 n-m+1趟,总比较次数最坏达 (n-m)+m = n
若每趟第 m个不匹配，总比较次数最坏亦达到 n
求 next函数的比较次数为 m,所以总的时间复杂度是 O(n+m)
