第四章 串
?4.1 串类型的定义
?4.2 串的表示和实现
? 4.2.1 定长顺序存储表示
? 4.2.2 堆分配存储表示
?4.3 串的模式匹配算法
? 讨论基本的串处理操作和两种存储结构
4.1 串类型的定义
?非数值处理的对象基本上是字符串数据
? 串 (string)(或称字符串 )----
? 由零个或多个字符组成的有限序列
? 记为, s = ?a1a2...an? (n>=0)
? ai(1<=i<=n)是字母,数字或其它字符
? n称为串的 长度,n=0的串称为 空串 (Null string)
? 子串 ----串中任意个连续字符组成的子序列
? 包含子串的串叫主串
? 子串在主串中的位置 ----
? 子串的第一个字符在主串中的序号
串的例子
?例如,a,b,c,d 四个字符串为
? a=?BEI?,b=?JING?
? c=?BEIJING?,d=?BEI JING?
? 它们的长度分别为 3,4,7,8
? a和 b都是 c和 d的子串
? a在 c和 d中的位置都是 1
? b在 c中的位置是 4,而 b在 d中的位置是 5
? 注意,单引号是为字符串区别于变量名而设,它不是字符串的内容
?称两个串是相等的 ---
? 当且仅当这两个串每个字符对应相等
串 的 抽 象 数 据 类 型
--- 数据对象为字符集的线性表
? ADT String {
? 数据对象,D = {ai | ai?CharacteSet,i=1,2,...n,n>=0}
? 数据关系,R1= {＜ ai-1.,aj＞ | ai?D,i=2,...n}。
? 基本操作：
? StrAssign(&T,chars); StrCopy(&T,S);
? StrEmpty (S); StrCompare(S,T);
? StrLength(S); ClearString(&S);
? Concat(&T,S1,S2); Substring(&Sub,S,pos,len);
? Index(S,T,pos); Replace(&S,T,V);
? StrInsert(&S,pos,T); StrDelete(&S,pos,len);
? DestroyString(&S)
? }ADT String
基本操作的功能说明 1
? StrAssign(&T,chars)
? 初始条件, chars是字符串常量。
? 操作结果, 生成一个其值等于 chars的串 T。
? StrCopy(&T,S)
? 初始条件, 字符串 S已经存在 。
? 操作结果, 由串 S复制得 串 T。
? StrEmpty (S)
? 初始条件, 字符串 S已经存在 。
? 操作结果, 若 S为空串，则返回 TRUE,否则返回 FALSE。
? StrCompare(S,T)
? 初始条件, 字符串 S和 T存在 。
? 操作结果, 若 S>T,则返回值 >0;若 S=T,则返回值 =0;否则返回
值 <0。
基本操作的功能说明 2
? StrLength(S)
? 初始条件, 字符串 S已经存在 。
? 操作结果, 返回串 S元素个数，称为串的长度。
? ClearString(&S)
? 初始条件, 字符串 S已经存在 。
? 操作结果, 将串 S清为空串。
? Concat(&T,S1,S2)
? 初始条件, 字符串 S1,S2已经存在 。
? 操作结果, 用 T返回由 串 S1和 S2联结而成的新串。
? Substring(&Sub,S,pos,len)
? 初始条件, 串 S存在,1<=pos<=S的长度,0<=len<=S的长度 -pos+1。
? 操作结果, 用 Sub返回串 S的第 pos个字符起长度为 len的子串。
基本操作的功能说明 3
? Index(S,T,pos)
? 初始条件, 串 S和 T存在,T是非空串,1<=pos<=S的长度 。
? 操作结果, 若主串 S中存在和串 T相同的子串，则 返回它在主串
S中第 pos个字符之后第一次出现的位置；否则返回０。
? Replace(&S,T,V)
? 初始条件, 字符串 S,T,V已经存在,T是非空串 。
? 操作结果, 用 V替换主串 S中出现的所有与 T相等的不重叠的子 串。
? StrInsert(&S,pos,T)
? 初始条件, 字符串 S,T存在,1<=pos<=S的长度 +1。
? 操作结果, 在串 S的第 pos个字符 之前插入串 T。
? StrDelete(&S,pos,len)
? 初始条件, 串 S存在,1<=pos<=S的长度 -len+1。
? 操作结果, 从串 S中删除 第 pos个字符起长度为 len的子串 。
? DestroyString(&S),把存在的串 S销毁。
串类型的最小操作子集
? 上述 13种基本操作中,下面 5种操作构成最小操作子集,
? 串赋值 StrAssign;
? 串比较 StrCompare;
? 求串长 StrLength;
? 串联结 Concat;
? 求子串 Substring;
? 其它操作可以用其实现
? 例如定位函数
? Index(S,T,pos)
? 的算法如右,
int Index(String S,String T,int pos)
{ int i,n,m; String sub;
if(pos > 0){
n = StrLength(S);
m = StrLength(T); i = pos;
while(i<=n-m+1){
SubString(sub,S,i,m);
if(StrCompare(sub,T)!=0)++i;
else return i;
} //while
} // if
return 0;
} // Index
4.2 串的表示和实现 (一 )
?4.2.1 定长顺序存储表示
? 用一组连续的存储单元存储串值的字符序列,
? 在 C语言中,用字符, \0”表示串的终结,“\0”不计入串长,
? 另一种方法是定长数组表示一个串,
#define MAXSTRLEN 255 // 串的长度最大为 255
typedef unsigned char SString[MAXSTRLEN+1];
// 0号单元存放串的长度,其最大值刚好是 255.
? 当超出 255个字符时,串的多余内容被舍去,叫做, 截断,
? 以下用串联结和求子串为例介绍这种存储
1.串联结 Concat(&T,S1,S2)的算法
status Concat(SString &T,SString S1,SString S2)
{//用 T返回由 串 S1和 S2联结而成的新串。若未被截断,则返回 1;否则返回 0。
if ( S1[0]+S2[0] <= MAXSTRLEN) { //未被截断
T[1..S1[0]] = S1[1..S1[0]]; // 示意赋值，非 C语句
T[S1[0]+1.,S1[0]+S2[0]] = S2[1..S2[0]]; // 示意赋值
T[0] = S1[0]+S2[0];
uncut = 1;
}elseif (S1[0] < MAXSTRLEN) { // 截断
T[1..S1[0]] = S1[1..S1[0]];
T[S1[0]+1.,MAXSTRLEN] = S2[1.,MAXSTRLEN-S1[0]];
T[0] = MAXSTRLEN;
uncut = 0;
}else{ // 截断 (仅取 S1)
T[0.,MAXSTRLEN] = S1[0.,MAXSTRLEN];
uncut = 0;
} // if
return uncut;
} // Concat
Concat(&T,S1,S2)的算法示意图
S1 S2
T
0 maxstrlen 0 maxstrlen
S1[0]+S2[0] <= MAXSTRLEN 时
S1 S2
T
0 maxstrlen 0 maxstrlen
S1[0]+S2[0] > MAXSTRLEN 时
截断部分
2.求子串 SubString(&Sub,S,pos,len)的算法
status SubString(SString &Sub,SString S,int pos,int len)
{//用 Sub返回串 S的第 pos个字符起长度为 len的子串 。
// 其中,1<=pos<=StrLength(S) 且 0<=len<=StrLength(S) -pos + 1 。
if ( pos < 1 || pos > s[0] || len < 0 || len > s[0] - pos +1 ) return ERROR;
Sub[1..len] = S[pos..pos+len-1]; // 示意赋值，非 C语句
Sub[0] = len;
return OK;
} // SubString
S
Sub
1 pos
len
串的表示和实现 (二 )
?4.2.2 堆分配存储表示
? 也是用一组连续的存储单元存储串值的字符序列,
? 但存储空间是在程序执行过程中动态分配得到的,
? 在 C语言中,用字符, \0”表示串的终结,“\0”不计入串长,
typedef struct{
char *ch; // 若是非空串,则按实际长度分配,否则为 NULL;
int length; // 串长度
} HString;
? 以下用串插入操作 StrInsert(&S,pos,T)
? 为例介绍这种存储
串插入 StrInsert(&S,pos,T)的算法
status StrInsert(HString &S,int pos,HString T)
{ // 1<=pos<=StrLength(S)+1。 在串 S的第 pos个字符 之前插入串 T。
if ( pos < 1 || pos > S.length) return ERROR; // pos 不合法
if(T.length) { // T 非空,则要重新分配空间,插入 T
if(!(S.cj = (char *)realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit(OVERFLOW);
for(i=S.length - 1; i>=pos-1; --i) // 为插入 T而腾出位置
S.ch[i+T.length] = S.ch[i];
S.ch[pos-1..pos+T.length-2] = T.ch[0..T.length-1]; // 插入 T
S.length += T.length;
} // if
return OK;
} // StrInsert
4.3 串的模式匹配算法
? 4.3.1求子串位置的定位函数 Index(S,T,pos)
? 采用定长顺序存储结构,不依赖其他串操作的匹配算法,
int Index(SString S,SString T,int pos)
{ // T是非空串,也称为模式,1<=pos<=S的长度 。
// 若主串 S中存在和模式 T相同的子串，则 返回它在主串
// S中第 pos个字符之后第一次出现的位置；否则返回０。
i = pos; j = 1;
while(i<=S[0] && j <= T[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; // 匹配不成功
}
简单匹配算法的匹配过程示例
? 例如 T=“abcac”; S=“ababcabcacbab”
? 第一趟匹配 a b a b c a b c a c b a b (i=3)
? a b c (j=3)
? 第二趟匹配 a b a b c a b c a c b a b (i=2)
? a (j=1)
? 第三趟匹配 a b a b c a b c a c b a b (i=7)
? a b c a c (j=5)
? 第四趟匹配 a b a b c a b c a c b a b (i=4)
? a (j=1)
? 第五趟匹配 a b a b c a b c a c b a b (i=5)
? a (j=1)
? 第六趟匹配 a b a b c a b c a c b a b (i=11)
? a b c a c (j=6) 成功 !
简单匹配算法的复杂度分析
? 设 n = StrLength(S);m = StrLength(T);
? 最好情况的复杂度为 O(n+m),如
? T =,STING”
? S =,A STRING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT”
? 最坏情况的复杂度为 O(n*m),如
? T =,00000001”
? S =,00000000000000000000000000000000000000000000000001”
模式匹配的一种改进算法 (KMP算法 )
? KMP算法的改进在于,
? 每一趟匹配过程中出现字符比较不等时,不需要回朔 i指针
? 只要利用已经, 部分匹配, 结果,调整 j指针,即将模式向
右滑动尽可能远的一段距离,来个提高算法效率,
? 上例的 KMP算法匹配过程示意如下
? 第一趟匹配 a b a b c a b c a c b a b (i=3)
? a b c (j=3)
? 第二趟匹配 a b a b c a b c a c b a b (i=3 -> 7)
? a b c a c (j=1 -> 5)
? 第三趟匹配 a b a b c a b c a c b a b (i=7 -> 11)
? (a)b c a c (j=2 -> 6)
? 显然算法复杂度为 O(n+m)
KMP算法的基本思想 (一 )
? 假设主串为 S=“s1s2...sn”,模式串为 T=“t1t2...tm”
? 我们要解决的问题是,当, 失配, (si?tj)时,模式
串 T”向右滑动, 的可行距离有多远 ;或者说,下一步
si应该与模式串中的哪个字符比较?
? 可以推断,答案将完全取决于模式串,而与主串无关
? 因此,可以预先为模式串设定一个数组 next[j],当
,失配, (si?tj)时,i不变,j改为 next[j]
? 前面例子的 next[j] 是, j 1 2 3 4 5
模式串 a b c a c
next[j] 0 1 1 1 2
KMP算法的匹配过程示例
? 另一个模式串的例子是,
? 任选一主串举例如下,
? 第一趟 a c a b a a b a a b c a c a a b c (i=2)
? a b (j=2,next[2]=1)
? 第二趟 a c a b a a b a a b c a c a a b c (i=2)
? a (j=1,next[1]=0)
? 第三趟 a c a b a a b a a b c a c a a b c (i=8)
? a b a a b c (j=6,next[6]=3)
? 第四趟 a c a b a a b a a b c a c a a b c (i=14)
? (a b)a a b c a c (j=9,成功 )
j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
KMP算法的基本思想 (二 )
? 一般情况下,模式串的 next函数的定义如下,
? 0 当 j=1时
? next[j]= max{k|1<k<j且,t1...tk-1”=“tj-k+1...tj-1”}
? 1 其他情况
? 如,
j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
KMP算法
? int Index_KMP(SString S,SString T,int pos)
? { // 利用模式串 T的 next函数求 T在主串
? // S中第 pos个字符之后第一次出现的位置；否则返回０。
? i = pos; 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; // 匹配不成功
? } // Index_KMP
求模式串的 next值的算法思想
? 用递推方法求 next函数值, next[1]=0;
? 设 next[j]=k,则有关系,“t1...tk-1”=“tj-k+1...tj-1”
? 其中 1<k<j,并且不可能存在 k’>k 使上述关系成立,
? 那么 next[j+1] =?,有两种情况,
?(1)若 tk=tj,则表明,“t1...tk”=“tj-k+1...tj”
? 并且不可能存在 k’>k 使上述关系成立,
? 这就是说 next[j+1]=k+1 或 next[j+1]=next[j]+1
?(2)若 tk ? tj,则表明,“t1...tk” ?“tj-k+1...tj”
? 此时求 next的问题可看成模式匹配的问题 ;
? 递推 k=next[k],直到 T[k]=T[j]或 k=0;
? 此时 next[j+1]=next[k]+1
求模式串的 next函数值
?Void get_next(Sstring T,int &next[])
?{ // 求模式串的 T的 next函数值并存入数组 next.
? j = 1; next[1] = 0; k = 0;
? while(j<T[0]){
? if(k==0||T[j]==T[k]){++j;++k;next[j]=k;}
? else k = next[k];
? }
?} //get_next
实验与习题
?理论习题 4.3,4.4,
? 求 4.7,4.8的 next函数值
?实验题,
? ① 4.17
? ② 4.25
? ?把教材中的算法 get_next和 Index_KMP
? 修改为用堆存储结构表示的串相对应的算法
?4.1 串类型的定义
?4.2 串的表示和实现
? 4.2.1 定长顺序存储表示
? 4.2.2 堆分配存储表示
?4.3 串的模式匹配算法
? 讨论基本的串处理操作和两种存储结构
4.1 串类型的定义
?非数值处理的对象基本上是字符串数据
? 串 (string)(或称字符串 )----
? 由零个或多个字符组成的有限序列
? 记为, s = ?a1a2...an? (n>=0)
? ai(1<=i<=n)是字母,数字或其它字符
? n称为串的 长度,n=0的串称为 空串 (Null string)
? 子串 ----串中任意个连续字符组成的子序列
? 包含子串的串叫主串
? 子串在主串中的位置 ----
? 子串的第一个字符在主串中的序号
串的例子
?例如,a,b,c,d 四个字符串为
? a=?BEI?,b=?JING?
? c=?BEIJING?,d=?BEI JING?
? 它们的长度分别为 3,4,7,8
? a和 b都是 c和 d的子串
? a在 c和 d中的位置都是 1
? b在 c中的位置是 4,而 b在 d中的位置是 5
? 注意,单引号是为字符串区别于变量名而设,它不是字符串的内容
?称两个串是相等的 ---
? 当且仅当这两个串每个字符对应相等
串 的 抽 象 数 据 类 型
--- 数据对象为字符集的线性表
? ADT String {
? 数据对象,D = {ai | ai?CharacteSet,i=1,2,...n,n>=0}
? 数据关系,R1= {＜ ai-1.,aj＞ | ai?D,i=2,...n}。
? 基本操作：
? StrAssign(&T,chars); StrCopy(&T,S);
? StrEmpty (S); StrCompare(S,T);
? StrLength(S); ClearString(&S);
? Concat(&T,S1,S2); Substring(&Sub,S,pos,len);
? Index(S,T,pos); Replace(&S,T,V);
? StrInsert(&S,pos,T); StrDelete(&S,pos,len);
? DestroyString(&S)
? }ADT String
基本操作的功能说明 1
? StrAssign(&T,chars)
? 初始条件, chars是字符串常量。
? 操作结果, 生成一个其值等于 chars的串 T。
? StrCopy(&T,S)
? 初始条件, 字符串 S已经存在 。
? 操作结果, 由串 S复制得 串 T。
? StrEmpty (S)
? 初始条件, 字符串 S已经存在 。
? 操作结果, 若 S为空串，则返回 TRUE,否则返回 FALSE。
? StrCompare(S,T)
? 初始条件, 字符串 S和 T存在 。
? 操作结果, 若 S>T,则返回值 >0;若 S=T,则返回值 =0;否则返回
值 <0。
基本操作的功能说明 2
? StrLength(S)
? 初始条件, 字符串 S已经存在 。
? 操作结果, 返回串 S元素个数，称为串的长度。
? ClearString(&S)
? 初始条件, 字符串 S已经存在 。
? 操作结果, 将串 S清为空串。
? Concat(&T,S1,S2)
? 初始条件, 字符串 S1,S2已经存在 。
? 操作结果, 用 T返回由 串 S1和 S2联结而成的新串。
? Substring(&Sub,S,pos,len)
? 初始条件, 串 S存在,1<=pos<=S的长度,0<=len<=S的长度 -pos+1。
? 操作结果, 用 Sub返回串 S的第 pos个字符起长度为 len的子串。
基本操作的功能说明 3
? Index(S,T,pos)
? 初始条件, 串 S和 T存在,T是非空串,1<=pos<=S的长度 。
? 操作结果, 若主串 S中存在和串 T相同的子串，则 返回它在主串
S中第 pos个字符之后第一次出现的位置；否则返回０。
? Replace(&S,T,V)
? 初始条件, 字符串 S,T,V已经存在,T是非空串 。
? 操作结果, 用 V替换主串 S中出现的所有与 T相等的不重叠的子 串。
? StrInsert(&S,pos,T)
? 初始条件, 字符串 S,T存在,1<=pos<=S的长度 +1。
? 操作结果, 在串 S的第 pos个字符 之前插入串 T。
? StrDelete(&S,pos,len)
? 初始条件, 串 S存在,1<=pos<=S的长度 -len+1。
? 操作结果, 从串 S中删除 第 pos个字符起长度为 len的子串 。
? DestroyString(&S),把存在的串 S销毁。
串类型的最小操作子集
? 上述 13种基本操作中,下面 5种操作构成最小操作子集,
? 串赋值 StrAssign;
? 串比较 StrCompare;
? 求串长 StrLength;
? 串联结 Concat;
? 求子串 Substring;
? 其它操作可以用其实现
? 例如定位函数
? Index(S,T,pos)
? 的算法如右,
int Index(String S,String T,int pos)
{ int i,n,m; String sub;
if(pos > 0){
n = StrLength(S);
m = StrLength(T); i = pos;
while(i<=n-m+1){
SubString(sub,S,i,m);
if(StrCompare(sub,T)!=0)++i;
else return i;
} //while
} // if
return 0;
} // Index
4.2 串的表示和实现 (一 )
?4.2.1 定长顺序存储表示
? 用一组连续的存储单元存储串值的字符序列,
? 在 C语言中,用字符, \0”表示串的终结,“\0”不计入串长,
? 另一种方法是定长数组表示一个串,
#define MAXSTRLEN 255 // 串的长度最大为 255
typedef unsigned char SString[MAXSTRLEN+1];
// 0号单元存放串的长度,其最大值刚好是 255.
? 当超出 255个字符时,串的多余内容被舍去,叫做, 截断,
? 以下用串联结和求子串为例介绍这种存储
1.串联结 Concat(&T,S1,S2)的算法
status Concat(SString &T,SString S1,SString S2)
{//用 T返回由 串 S1和 S2联结而成的新串。若未被截断,则返回 1;否则返回 0。
if ( S1[0]+S2[0] <= MAXSTRLEN) { //未被截断
T[1..S1[0]] = S1[1..S1[0]]; // 示意赋值，非 C语句
T[S1[0]+1.,S1[0]+S2[0]] = S2[1..S2[0]]; // 示意赋值
T[0] = S1[0]+S2[0];
uncut = 1;
}elseif (S1[0] < MAXSTRLEN) { // 截断
T[1..S1[0]] = S1[1..S1[0]];
T[S1[0]+1.,MAXSTRLEN] = S2[1.,MAXSTRLEN-S1[0]];
T[0] = MAXSTRLEN;
uncut = 0;
}else{ // 截断 (仅取 S1)
T[0.,MAXSTRLEN] = S1[0.,MAXSTRLEN];
uncut = 0;
} // if
return uncut;
} // Concat
Concat(&T,S1,S2)的算法示意图
S1 S2
T
0 maxstrlen 0 maxstrlen
S1[0]+S2[0] <= MAXSTRLEN 时
S1 S2
T
0 maxstrlen 0 maxstrlen
S1[0]+S2[0] > MAXSTRLEN 时
截断部分
2.求子串 SubString(&Sub,S,pos,len)的算法
status SubString(SString &Sub,SString S,int pos,int len)
{//用 Sub返回串 S的第 pos个字符起长度为 len的子串 。
// 其中,1<=pos<=StrLength(S) 且 0<=len<=StrLength(S) -pos + 1 。
if ( pos < 1 || pos > s[0] || len < 0 || len > s[0] - pos +1 ) return ERROR;
Sub[1..len] = S[pos..pos+len-1]; // 示意赋值，非 C语句
Sub[0] = len;
return OK;
} // SubString
S
Sub
1 pos
len
串的表示和实现 (二 )
?4.2.2 堆分配存储表示
? 也是用一组连续的存储单元存储串值的字符序列,
? 但存储空间是在程序执行过程中动态分配得到的,
? 在 C语言中,用字符, \0”表示串的终结,“\0”不计入串长,
typedef struct{
char *ch; // 若是非空串,则按实际长度分配,否则为 NULL;
int length; // 串长度
} HString;
? 以下用串插入操作 StrInsert(&S,pos,T)
? 为例介绍这种存储
串插入 StrInsert(&S,pos,T)的算法
status StrInsert(HString &S,int pos,HString T)
{ // 1<=pos<=StrLength(S)+1。 在串 S的第 pos个字符 之前插入串 T。
if ( pos < 1 || pos > S.length) return ERROR; // pos 不合法
if(T.length) { // T 非空,则要重新分配空间,插入 T
if(!(S.cj = (char *)realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit(OVERFLOW);
for(i=S.length - 1; i>=pos-1; --i) // 为插入 T而腾出位置
S.ch[i+T.length] = S.ch[i];
S.ch[pos-1..pos+T.length-2] = T.ch[0..T.length-1]; // 插入 T
S.length += T.length;
} // if
return OK;
} // StrInsert
4.3 串的模式匹配算法
? 4.3.1求子串位置的定位函数 Index(S,T,pos)
? 采用定长顺序存储结构,不依赖其他串操作的匹配算法,
int Index(SString S,SString T,int pos)
{ // T是非空串,也称为模式,1<=pos<=S的长度 。
// 若主串 S中存在和模式 T相同的子串，则 返回它在主串
// S中第 pos个字符之后第一次出现的位置；否则返回０。
i = pos; j = 1;
while(i<=S[0] && j <= T[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; // 匹配不成功
}
简单匹配算法的匹配过程示例
? 例如 T=“abcac”; S=“ababcabcacbab”
? 第一趟匹配 a b a b c a b c a c b a b (i=3)
? a b c (j=3)
? 第二趟匹配 a b a b c a b c a c b a b (i=2)
? a (j=1)
? 第三趟匹配 a b a b c a b c a c b a b (i=7)
? a b c a c (j=5)
? 第四趟匹配 a b a b c a b c a c b a b (i=4)
? a (j=1)
? 第五趟匹配 a b a b c a b c a c b a b (i=5)
? a (j=1)
? 第六趟匹配 a b a b c a b c a c b a b (i=11)
? a b c a c (j=6) 成功 !
简单匹配算法的复杂度分析
? 设 n = StrLength(S);m = StrLength(T);
? 最好情况的复杂度为 O(n+m),如
? T =,STING”
? S =,A STRING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT”
? 最坏情况的复杂度为 O(n*m),如
? T =,00000001”
? S =,00000000000000000000000000000000000000000000000001”
模式匹配的一种改进算法 (KMP算法 )
? KMP算法的改进在于,
? 每一趟匹配过程中出现字符比较不等时,不需要回朔 i指针
? 只要利用已经, 部分匹配, 结果,调整 j指针,即将模式向
右滑动尽可能远的一段距离,来个提高算法效率,
? 上例的 KMP算法匹配过程示意如下
? 第一趟匹配 a b a b c a b c a c b a b (i=3)
? a b c (j=3)
? 第二趟匹配 a b a b c a b c a c b a b (i=3 -> 7)
? a b c a c (j=1 -> 5)
? 第三趟匹配 a b a b c a b c a c b a b (i=7 -> 11)
? (a)b c a c (j=2 -> 6)
? 显然算法复杂度为 O(n+m)
KMP算法的基本思想 (一 )
? 假设主串为 S=“s1s2...sn”,模式串为 T=“t1t2...tm”
? 我们要解决的问题是,当, 失配, (si?tj)时,模式
串 T”向右滑动, 的可行距离有多远 ;或者说,下一步
si应该与模式串中的哪个字符比较?
? 可以推断,答案将完全取决于模式串,而与主串无关
? 因此,可以预先为模式串设定一个数组 next[j],当
,失配, (si?tj)时,i不变,j改为 next[j]
? 前面例子的 next[j] 是, j 1 2 3 4 5
模式串 a b c a c
next[j] 0 1 1 1 2
KMP算法的匹配过程示例
? 另一个模式串的例子是,
? 任选一主串举例如下,
? 第一趟 a c a b a a b a a b c a c a a b c (i=2)
? a b (j=2,next[2]=1)
? 第二趟 a c a b a a b a a b c a c a a b c (i=2)
? a (j=1,next[1]=0)
? 第三趟 a c a b a a b a a b c a c a a b c (i=8)
? a b a a b c (j=6,next[6]=3)
? 第四趟 a c a b a a b a a b c a c a a b c (i=14)
? (a b)a a b c a c (j=9,成功 )
j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
KMP算法的基本思想 (二 )
? 一般情况下,模式串的 next函数的定义如下,
? 0 当 j=1时
? next[j]= max{k|1<k<j且,t1...tk-1”=“tj-k+1...tj-1”}
? 1 其他情况
? 如,
j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
KMP算法
? int Index_KMP(SString S,SString T,int pos)
? { // 利用模式串 T的 next函数求 T在主串
? // S中第 pos个字符之后第一次出现的位置；否则返回０。
? i = pos; 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; // 匹配不成功
? } // Index_KMP
求模式串的 next值的算法思想
? 用递推方法求 next函数值, next[1]=0;
? 设 next[j]=k,则有关系,“t1...tk-1”=“tj-k+1...tj-1”
? 其中 1<k<j,并且不可能存在 k’>k 使上述关系成立,
? 那么 next[j+1] =?,有两种情况,
?(1)若 tk=tj,则表明,“t1...tk”=“tj-k+1...tj”
? 并且不可能存在 k’>k 使上述关系成立,
? 这就是说 next[j+1]=k+1 或 next[j+1]=next[j]+1
?(2)若 tk ? tj,则表明,“t1...tk” ?“tj-k+1...tj”
? 此时求 next的问题可看成模式匹配的问题 ;
? 递推 k=next[k],直到 T[k]=T[j]或 k=0;
? 此时 next[j+1]=next[k]+1
求模式串的 next函数值
?Void get_next(Sstring T,int &next[])
?{ // 求模式串的 T的 next函数值并存入数组 next.
? j = 1; next[1] = 0; k = 0;
? while(j<T[0]){
? if(k==0||T[j]==T[k]){++j;++k;next[j]=k;}
? else k = next[k];
? }
?} //get_next
实验与习题
?理论习题 4.3,4.4,
? 求 4.7,4.8的 next函数值
?实验题,
? ① 4.17
? ② 4.25
? ?把教材中的算法 get_next和 Index_KMP
? 修改为用堆存储结构表示的串相对应的算法
