第四章 串
,数据结构,
第四章 串第 2页主要内容
1,串的逻辑结构
2,串的基本操作
3,串的链式存储结构
4,串的堆存出结构
5,串的顺序存储结构
6,静态结构存储串时的操作第四章 串第 3页主要内容
静态结构存储串时的操作（ Index函数）
朴素的模式匹配算法（ BF算法）
改进的模式匹配算法（ KMP算法）
求模式串 next函数值的算法
求模式串 next函数值的修正算法
next函数的性质
示例与模式匹配
7.模式匹配（ 重点 ）
第四章 串第 4页第四章 串串（又称字符串）是一种特殊的 线性表,它的每个结点仅由一个字符组成
。
本章将讨论串的有关概念、结构、
存储方法和串的基本运算及其实现。
第四章 串第 5页定义,串（ String）是零个或多个字符组成的有限序列。
一般记为,S=‘a1a2···a n’ (n≥0).
术语
1） 串名,S.
2） 串值,'a1a2···a n',ai(1≤i≤n).
3） 串的长度,串中所包含的字符个数，如串
'abcde'的长度为 5,
串的逻辑结构第四章 串第 6页
4） 空串,长度为 0(n=0)的串，它不包含任何字符，记作 S=''(或 S=φ).
5） 空格串,由空格符 (ASCII值 32)组成的串，
如 S=‘’.注意 S= '?'与 S=''不同，前者是长度为 1的非空串，它含有一个空格字符，而后者是长度为 0的空串。
6） 子串,串中任意个连续的字符组成的子序列
。比如 'abcde'中的 'bcd'.
串的逻辑结构第四章 串第 7页用二元组的形式来定义串,串是一个二元组,
string = ( D,R )
其中
D={ai|ai∈ 字符集,i=1,2,···,n,n≥0}
R={N}
有序偶的集合 N={<ai-1,ai>| ai-1,ai ∈ D,i=2,3,···n}
故串的逻辑结构和线性表极为相似。区别仅在 D
的定义上。 线性表的数据对象可以是 任意数据类型,
而串的数据对象是 字符集 。
串是几种最简单的数据结构之一。
串的逻辑结构第四章 串第 8页串虽然是一种特殊的线性表，但由于存储结构有所不同，故其基本操作也不同。
1、基本操作子集不同，比如串包含有联接、求子串等操作
2、操作对象不同，线性表的操作通常以 数据元素或结点 为操作对象，而串的操作主要以串的 整体 为操作对象。
1）赋值操作
Assign(s,t) s为串名,t为字符串变量。
Create(s,ss) s为串名,ss为字符序列。
2）判等函数
Equal(s,t) 返回布尔值 true或 false.s,t可为非空串或空串。
3）求串长函数
Length(s) 返回串 s字符的个数。
4）联接函数
Concat(s,t) 返回由串 s,t相联接而成的新串。联接运算不满足交换律，但满足结合律。
串的基本操作第四章 串第 9页
5） 求子串函数
Substr(S,start,len) 返回从串 S中第 start个字符起，长度为
len的字符序列。
要求 1≤start≤Length(s)+1,
0≤len≤ Length(s)-start+1.
6）定位函数
Index(s,t)
返回串 t在串 s中第一次出现时的串首位置，若未出现，则返回值 0，要求 t不能是空串。
7）置换操作
Replace(s,t,v)
以串 v替换所有在串 s中出现的和非空串 t相等的子串。
串的基本操作第四章 串第 10页
串的基本操作
8）插入（前插）操作
Insert(s,pos,t)
在串 s的第 pos个字符之前插入串 t,要求 1≤pos≤Length(s)+1。
注,Insert(S,Length(s)+1,t) 与 Concat(s,t)功能相同，
即当 pos= Length(s)+1时,t将插入至 s的尾部之后。
9）删除操作
Delete(s,pos,len)
从串 s中删去从第 pos个字符起，长度为 len的子串。要求
1≤pos≤Length(s)，
且 1≤len≤Length(s)-pos+1。
说明：可将 1)至 5)定义为串的基本操作,6)至 9)可由基本操作加以实现。
第四章 串第 11页示例 1 用串的基本操作 (1)至 (5)实现定位函数 Index(s,t)。
int Index( string s,string t )
/*若串 s中存在和 t相等的子串，则返回第一个子串在主串中的位置，否则返回零 */
{ n = Length(s); m = Length(t); i = 1; //m不等于 0
while( i ≤ n-m+1 )
if( Equal( Substr( s,i,m ),t ))
return i;
else i++;
return 0;
} //index
串的基本操作第四章 串第 12页
C中预定义字符串标准函数和标准过程字符串标准函数函数名 意 义 结果类型
strcat 连接字符串序列 char *
strcpy 复制一个字符串 char *
strlen 返回串的动态长度 int
还有,strcmp,strcmpi,strrchr,… …
参见：
String.h
串的基本操作第四章 串第 13页用线性链表的方式存储串值结点大小问题
串的 链式 存储结构
D A T A S ^
head
1）结点大小等于 1，即一个结点存放一个字符优点,便于实现插入、删除等操作缺点,浪费存储空间，存储利用率最多 1/2
DA T A S TR UCTU RES ^
head
2）结点大小等于 4，即一个结点存放 4个字符优点,存储效率较高缺点,实现插入、删除等操作较复杂
^H
第四章 串第 14页用块链结构存储串值为便于进行串的操作，当以链表存储串值时,给出头、尾指针，加当前串的长度 。称如此定义的 串存储结构为块链结构
。
设尾指针的目的是为了便于进行联接操作。
块链结构的说明
#define CHUNK_SIZE 1000 //用户定义的结点大小
typedef struct {
char ch[CHUNK_SIZE]; //块大小
chunk *next; //指针
} chunk;
typedef struct {
chunk *head,*tail; //头、尾指针
int length; //长度
} LString;
LString clst;
串的 链式 存储结构第四章 串第 15页
clst 15
DA T A S TR UCTU RES # ^
头 尾 长度块链结构示意图
串的 链式 存储结构用块链结构存储串值串值所占存储空间存储密度 = —————————— < 1
实际分配的存储空间这种存储方式对某些操作比较方便，总的来说仍较复杂。
第四章 串第 16页特点,每个串的串值各存储在一组 地址连续的存储 单元中，但它们的存储地址是在程序执行过程中 动态分配 而得。
typedef struct{
char *ch;
int length;
}HString;
使用时必须分配 (malloc)和回收 (free)内存。
串的 堆 存储结构用堆结构存储串值第四章 串第 17页
21
15
··· A STRING OF LENGTH 21F
··· DATA STRUCTURES ···
Heap
s1
串的动态分配存储结构示意图起始地址起始地址
free
length ch
Free是指尚未分配内存地址
串的 堆 存储结构
s2
定义
HString s1
HString s2
第四章 串第 18页
1、赋值操作 Assign(s,t)
Status Assign( HString &t; char *s )
{ //将 s串的值赋给 t串
if( s.ch ) free( t.ch );
for( i=0,c=s; c; i++,c++ ); //求 s的长度
if( !i ){ t.ch = NULL; t.length = 0;}
else{
if(!(t.ch=(char*)malloc(i*sizeof(char))))
return OVERFLOW;
t.ch[0..i-1] = s[0..i-1];
t.length = i;
}
return OK;
}
算 法 4.9
串的 堆 存储结构第四章 串第 19页
2、联接运算 Concat
Status Concat( HString &t,HString s1,HString s2 )
{ //连接 s1,s2到 t中
if( t.ch ) free( t.ch ); //释放原空间
if(!(t.ch=(char*)malloc(s1.length+s2.length)*sizeof(char))))
return OVERFLOW; //分配空间
t.ch[0..s1.length-1] = s1.ch[0..s1.length-1]; //处理 s1
t.length = s1.length + s2.length; //长度
t.ch[s1.length..t.length-1] = s2.ch[0..s2.length-1]; //s2
}
串的 堆 存储结构第四章 串第 20页
3、求子串函数 Substr
Status SubStr( HString &sub,HString s,int pos,int len )
{ //从 s的 pos位置取 len长的子串，由 sub返回
if(pos<1||pos>s.length||len<0||len>s.length-pos+1)
return ERROR; //非法
if( sub.ch ) free( sub.ch ); //释放原有空间
if( !len ){ sub.ch = NULL; sub.length = 0 } //空串
else{
sub.ch = (char*)malloc(len*sizeof(char)); //分配空间
sub.ch[0..len-1] = s[pos-1..pos+len-2]; //取子串
sub.length = len;
}
return OK;
}
串的 堆 存储结构第四章 串第 21页
用一组 地址连续 的存储单元来存储串的字符序列。
每个字符占用一个 字节（ Byte） 。串中相邻的字符顺序地存放在相邻的字节中。
D A T A S T R U C T U R E S
l+1 l+2l l+15......
串的定长顺序存储结构定长顺序存储结构串定义：
#define maxlen 255 //允许最大的长度
typedef unsigned char String[maxlen+1]; //下标 0存放长度实现,串的联接函数,求子串的函数,求子串位置的定位函数第四章 串第 22页其中 L,s,t是 String；
[分析 ] 相当于求 L=s+t，若 s与 t连接后的串值长度超过 maxlen，则超过部分将被截断。 运算结果有三种可能情况。
1) length(s) + length(t) ≤ maxlen
Length(s)
s.ch
Length(t)
t.ch
定长顺序存储时的操作
1、串的联接函数 Concat(L,s,t)
L,ch
maxlenLength(L)
可得到串 L的正确结果第四章 串第 23页
Length(s)
s.ch
Length(t)
t.ch
定长顺序存储时的操作
2) length(s) + length(t) > maxlen而 length(s) < maxlen
需将 t的一部分截断，所得串 L中包含 s的全部与 t的一个子串
L,ch
maxlenLength(L)
t中被截去的字符序列第四章 串第 24页
Length(s)
s.ch
Length(t)
t.ch
L.ch
maxlenLength(L) t串被全部截去
3) length(s)=maxlen
得到的串 L是 s的串。
定长顺序存储时的操作第四章 串第 25页
Status Concat( string &L,string s,string t )
{ /*返回 s和 t联接的结果,s和 t的值不变。 */
switch{
case length(s) + length(t)≤maxlen,//正常联接
L[1.,length(s)] = s[1.,length(s)];
L[length(s)+1.,length(s)+ length(t)] = t[1.,length(t)];
L[0] = s[0] + t[0];
overflow = false;
case length(s)<maxlen://串 t截尾
overflow = true;
L[1.,length(s)] = s[1.,length(s)];
L[length(s)+1..maxlen] = t[1..maxlen - length(s)];
L[0] = maxlen;
default,//串中只含 s
overflow = true; L[1..maxlen] = s[1..maxlen]; L[0] = maxlen;
}; //switch
return overflow;
} // 算 法 4.2
定长顺序存储时的操作第四章 串第 26页
[分析 ] 复制字符序列，若 1≤start≤length(s)+1且 0≤len≤length(s)-
start+1，则将串 s从第 start个字符起长度为 len的子串赋给串 sub,并返回函数值 true，否则返回函数值 false，而 sub无确定值，为非法串。
Status Substr( string &sub,string s,int start,int len )
{ if((1≤start && start ≤length(s)+1) &&
(0≤len && len ≤length(s)-start+1))
{ sub.ch[1..len] = s.ch[start..start+len-1];
sub[0] = len;
return true;
}
return false;
} //substr 算 法 4.3
定长顺序存储时的操作
2、求子串的函数 Substr(sub,s,start,len).
第四章 串第 27页设有两个串
s = 's1s2···sn'
p = 'p1p2···pm' (0<m≤n)
称主串 S为目标（串）,子串 p为模式（串） 。
串的 模式匹配,在目标 S中寻找模式为 p的子串的过程,
串模式匹配的结果：
（ 1） 成功,Index(S,p) > 0
（ 2） 失败,Index(S,p) == 0
其中 Index返回第一个模式为 p的子串在主串 s中的位置。
定长顺序存储时的操作
3、求子串位置的定位函数 Index(s,p)
模式匹配算法，其中 p为模式第四章 串第 28页
定长顺序存储时的操作
3、求子串位置的定位函数 Index(s,p)
使用串的基本操作 (如 Equal,Length,Substr等 )实现求子串位置的定位函数 Index(s,p)的算法：
int Index( string s,string p )
{ n = Length(S);
m = Length(p);
i = 1;
while( i ≤ n – m + 1 )
if( Equal(Substr(S,i,m),p))
return i;
else i++;
return 0;
} //index
第四章 串第 29页根据上面算法的基本思想，可以写出一种不依赖于其他串基本操作的模式匹配算法 —— 朴素的模式匹配算法（
Brute-Force算法）。
BF算法的基本思想,用 p中字符依次与 s中字符比较
，以指示器 i,j分别指向 s,p。 ① 初始时令 i=1,j=1。 ② 若有
s[i]==p[j]，则令 i,j分别加 1，继续比较。当
j==(length(p)+1)，则匹配成功，返回相应的位置值。 ③
若在某时刻有 s[i]≠p[j]，则 i回退到 i-(j-1)+1=i-j+2处，令 j=1
，再进行逐个字符比较。 ④ 若直到 i>length(s)时尚未匹配成功，则表示匹配失败,返回值 0。
定长顺序存储时的操作
3、求子串位置的定位函数 Index(s,p)
朴素的模式匹配算法（ BF算法）
第四章 串第 30页
定长顺序存储时的操作
3、求子串位置的定位函数 Index(s,p)
朴素的模式匹配算法（ BF算法）
int Index_BF( string s,string p )
{ //求模式串 t在主串 s中位置的定位函数
i=1;j=1; //指针初始化
while( i≤length(s) && j≤length(p))
if( s[i] == p[j] )
{ i++； j++ } //继续比较后继字符
else
{ i = i-j+2； j = 1 }; //指针后退重新开始匹配
if( j > length(p))
return( i – length(p)); //匹配成功，返回定位序号
else
return(0); //匹配失败，返回值 0
}; //index_BF 算 法 4.4
第四章 串第 31页示例 1 设 s='ababcabcacbab',p='abcac'，求函数
Index_BF(s,p)的值。
算法 Index_BF的匹配过程如下：
第一趟匹配 ababcabcacbab { j 返回至 1,i返回至 i-j+2=3-3+2=2}
abc? j=3
第二趟匹配 ababcabcacbab { j 返回至 1,i返回至 i-j+2=2-1+2=3}
a? j=1
第三趟匹配 ababcabcacbab { j返回至 1,i 返回至 i-j+2=7-5+2=4}
abcac? j=5
↓i=3
↓i=2
↓i=7
朴素的模式匹配算法（ BF算法）
第四章 串第 32页第四趟匹配 ababcabcacbab {j返回至 1,i返回至 i-j+2=4-1+2=5}
a? j=1
第五趟匹配 ababcabcacbab {j返回至 1,i返回至 i-j+2=5-1+2=6}
a? j=1
第六趟匹配 ababcabcacbab {j>length(t)(6>5)匹配成功，返回 }
定位 abcac? j=6
算法的匹配过程
↓i=4
↓i=5
↓i=11
朴素的模式匹配算法（ BF算法）
第四章 串第 33页算法复杂性分析
● 一般情况,设
S='A STRING SEARCHING EXAMPLE CONSISTING'
+ 'OF SIMPLE TEXT' (n=52)
p='STING' (m=5)
BF算法执行 while语句中循环体的次数（即进行单个字符比较的次数）为
(index+length(p)-1)+4
=(33+5-1)+4
=41.
即除了主串中下划线的 4个字符均比较了 2次以外，其他字符均只和模式进行了 1次比较。
时间复杂度为 O(n+m)，这里 n是 s的长度,m是 p的长度,
Index=33
↓
第四章 串第 34页
● 特殊情况,设
S='OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO'
+’OOOOOOOOOOOO1’ (n=53)
p=’OOOOOOO1’ (m=8)
BF算法执行 while语句中循环体的次数（即进行单个字符比较的次数）为
index× m=46× 8=368.
故 BF算法在最坏情况下的时间复杂度为 O(n× m)，这里 n
是 s的长度,m是 p的长度,
算法效率差的原因：指针 i的 多次回溯 。而这些回溯并非是必须的。
Index=46
算法复杂性分析第四章 串第 35页示例 4 设 s=`abbaba`,p=`aba`,则 BF算法的匹配过程如下第一趟匹配 abbaba j返至 1,i返至 i-j+2=3-3+2=2
1) aba
第二趟匹配 abbaba j返至 1,i返至 i-j+2=2-1+2=3
2) a
第三趟匹配 abbaba j返至 1,i返至 i-j+2=3-1+2=4
3) a
第四趟匹配 abbaba j>length(p)(4>3)，匹配成功，返回定位
4) aba 序号 i-length(p)=7-3=4
↓i=3
↓i=2
↓i=3
↓i=7
↑j=3
↑j=1
↑j=1
↑j=4
改进的模式匹配算法（ KMP算法）
问题,①是否有不必要的回溯，即有没有冗余信息？
②是否可以不回溯？
③能否每次将模式向右”滑动,1位改成”滑动“尽可能的一段距离后，继续进行比较？
第四章 串第 36页讨论①
由 1) 知 p1=s1,p2=s2,p3≠s3
知 p1≠p2，故 p1≠s2，所以将 p右移 1位后的比较一定不等，即步骤 2) 是不必要的。
再由 p1=p3，可以推出 p1≠s3，所以将 p再右移 1位后的比较也一定不等，即步骤 3)亦是不必要的。
结论,在朴素算法中未利用部分有用信息。在此例中，由步骤
1) 便可直接将 p右移 3位，跳至步骤 4)，从 p1和 s4开始继续比较。
第一趟匹配 abbaba 将 t右移 3位
aba
第二趟匹配 abbaba 匹配成功
aba
↓i=3
↓i=7
↑j=3
↑j=4
改进的模式匹配算法（ KMP算法）
第四章 串第 37页讨论②
不回溯是可能的,因为模式不可能全在 si之前，模式只可能在 si 前后或全在 si 之后。故可另辟新路,i不回溯，而令模式串向右“滑动”。
讨论③
当某个字符比较不相等时,模式 p究竟应向右“滑动”至哪个位置再继续比较？或者说 模式 p要移动多少位？（在朴素算法中 p每次右移 1位）
KMP算法 （ D.E.Knuth,J.H.Morris,V.R.Pratt）的改进在于：
每当一趟匹配过程中出现字符不等时，不需回溯 i指针，而是 利用 已经得到的,部分匹配,的结果，将模式向右,滑动,尽可能远的一段距离后，继续进行匹配比较 。
改进的模式匹配算法（ KMP算法）
第四章 串第 38页再看示例 1
s=`ababcabcacbab`
p=`abcac`
第一趟匹配 ababcabcacbab 仅需要将模式向右移动两个字符的
abc 位置继续进行 i=3,j=1时的字符比较第二趟匹配 ababcabcacbab 在 i=4和 j=1,i=5和 j=1和 i=6和 j=1这
abcac 三次比较都是不必进行的第三趟匹配 ababcabcacbab 匹配成功！
(a)bcac
图 4.4 改进算法的匹配过程示例在整个匹配的过程中,i指针没有回溯。
↓i=3
↓i=3
↑j=3
↑j=1
↑j=2
↓i=7
↑j=5
↑i=7 ↑i=11
↑j=6 图 4.4 参见教材 p.80
第四章 串第 39页三条规则
1）若模式中第一个字符就与 si不同（ p1≠si），则将 si+1与 p1继续比较（或 si与 p0相比较）；否则
2）若模式中有 左子串 =右子串,即 ` p1··· pk-1`=` pj-k+1··· pj-1`，
则将 si与 pk继续比较；
3）若模式中无 左子串 =右子串,则令 si与 p1继续比较。
再看示例 4，运用上述诸规则 s=`abbaba`,p=`aba`
第一趟匹配 abbaba 规则 3）,si(i=3)与 p1继续比较
aba
第二趟匹配 abbaba 规则 1）,si+1(i=3)与 p1继续比较
a
第三趟匹配 abbaba 匹配，得序号 i-length(p)=7-3=4
aba
↓i=3
↑j=4
↓i=7
↑j=3
↑j=1
改进的模式匹配算法（ KMP算法）
第四章 串第 40页按三条规则再看示例 1
S=`ababcabcacbab`
p=`abcac`
第一趟匹配 ababcabcacbab
abc 规则 3）,si(i=3)与 p1继续比较第二趟匹配 ababcabcacbab
abcac 规则 2）,si(i=7)与 p2继续比较第三趟匹配 ababca bcacbab
(a)bcac 匹配成功！
↓i=3
↑j=3
↓i=7
↓i=11
↑j=5
↑j=6
第四章 串第 41页设主串 s=`s1s2···sn`,
模式串 p=`p1p2···pm` (0<m≤n).
问题：当匹配过程中产生失配（即 si≠pj)时,si（ i指针不回溯）应与模式中哪个字符再继续比较，即模式串可“向右滑动”多远距离？
设此时 si应与 pk(k<j)继续比较
s1 s2 · · · si · · · sn
··· pk ··· pj
则有
S1 S2 · · · Si-k+1 Si-k+2 · · · Si-1 Si · · · Sn
p1p2 · · · pk-1pk · · · pj
`p1p2 ··· pk-1`= `Si-k+1 Si-k+2 ··· Si-1` (4-2)
K-1个
K-1个
求模式串的 next函数第四章 串第 42页另外，由于 si≠pj，则已经得到的“部分匹配”结果是
S1 S2 · · · Si-j+1 Si-j+2 · · · Si-k+1 Si-k+2 · · · Si-1 Si · · ·
P1 P2 · · · Pj-k+1 Pj-k+2 · · · Pj-1 Pj
其中紧靠 si（或 pj）的 k-1个对应字符都相等
`Pj-k+1 Pj-k+2 · · · pj-1`= `Si-k+1 Si-k+2 · · · Si-1 ` (4-3)
由 (4-2),(4-3)，可推得
`P1P2 · · · Pk-1`=Pj-k+1 Pj-k+2 · · · Pj-1` (4-4)
反之，只要满足 (4-4)式，则 Si可与 Pk继续比较。但请注意，应当寻找最大可能的左子串 =右子串,以确定最大可能的 k.
K-1个
j-1个
求模式串的 next函数第四章 串第 43页示例 6 设模式串 P=`abaabcac`，则可得如下之 next函数值
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
注 1.必有 next[j]<j.
注 2,Next[j]（即 k）值只取决于模式串 p本身，而与目标串 S无关系令 next[j]=k,next[j]表明当模式中第 j个字符与主串中相应字符
“失配”时，在模式中需重新和主串中该字符进行比较的字符的 位置 。这是一个函数关系，称作 模式串的 next函数。 由前述的讨论知
：
)(,1
)` } (```1{
),(1,0
][
1
1111
111
继续比较与其它情况继续比较与且继续比较与即与则令就不匹配与时当
PS
PSPPPPjkkM a x
PSPSPSj
jn e x t
i
kijkjk
oiii
第四章 串第 44页示例 7 利用模式的 next函数进行匹配的过程
S=`acabaabaabcacaabc`
P=`abaabcac`
第一趟匹配 acabaaba···
ab next[2]=1
第二趟匹配 acabaaba···
a next[1]=0
第三趟匹配 acabaabaab···
abaabc next[6]=3
第四趟匹配 acabaabaabcacaabc···
abaabcac
匹配，得序号 index(s,p)=i-length(p)=14-8=6.
↓i=2
↑j=2
↑j=1
↑j=1 ↑j=6
↑j=3 ↑j=9
↓i=2
↓i=3 ↓i=8
↓i=8 ↓i=14
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
求模式串的 next函数第四章 串第 45页基于 next函数的匹配移位规则：
设 i,j分别指示主串和模式串中正待比较的字符，
初值 i=1,j=1.
1) 若 Si=Pi，则 i,j分别加 1，返至 1)；
2) 若 Si≠Pi，则 j退到 next[j]位置再比较，
a.当 j>0，则返至 1)；
b.当 j=0（即模式的第一个字符“失配”），则令
i加
1,j加 1（即 j=1），返至 1)；
如此继续，直至 匹配成功 (j>length(t))，并进而获得定位序号，或者 匹配失败 (i>length(s)而 j≤length(t)).
求模式串的 next函数第四章 串第 46页
KMP算法的实现
int index_KMP( SString s,SString t )
{ //利用模式串的 next函数求模式串 t在主串 S中位置的 KMP算法
i = 1; j = 1; //指针初始化
while((i≤length(s)) && (j≤length(t)))
if((j==0)||(s[i]==t[j]))
{i++;j++} //继续下一对字符的比较
else j = next[j]; //模式串向右滑动
if( j > length(t))
return(i-length(t)); //匹配成功
else
return(0);
} //index_KMP 算 法 4.5
第四章 串第 47页注 1,KMP算法是在已知模式串的 next函数值的基础上执行的，故其前提是假定已有求得模式串的 next函数值的算法。
注 2,算法中 j=0表明 Si与 P1就不匹配，故令 i加 1,j
加 1(0+1=1)，即令 Si+1与 P1继续比较。
注 3,算法分析（时间复杂度）,(1)该算法执行过程中 i只增不减,由 i初值为 1，循环过程中保持 i≤n，所以循环体中 i++最多执行 n次； （ 2） 另外 j的初值为 1，
而循环体中保持 j>0,由于 next[j]<j，所以 j=next[j]的 最多执行次数也不超过 n,故上述算法的时间复杂度为 O(n)
。
第四章 串第 48页算法思想可以从分析其定义出发，用递推的方法求得 next函数。
1)由定义知
next[1]=0 (4-6)
2)设 next[j]=k(1<k<j，最大的 k)，
`P1···P k-1`=`Pj-k+1···P j-1` (4-7)
今求 next[j+1]?
a,若 Pk=Pj，则由 (4-7)而得
`P1···P k`=`Pj-k+1···P j` (4-8)
即 next[j+1]=k+1=next[j]+1 (4-9)
b,若 Pk≠Pj,则
`P1···P k` ≠ `Pj-k+1···P j`
而将 `Pj-k+1···P j`看作主串。 Pj应与 Pnext[k]继续比较。记 next[k]=k`,若 Pj=Pk`，则有
`P1···P k``=`Pj-k`+1···P j`(1<k`<k<j) (4-10)
即 next[j+1]=k`+1，亦即
next[j+1]=next[k]+1 (4-11)
而若 Pj≠Pk`，则将模式继续向右滑动,Pj应与 Pnext[k`]继续比较。 ··· ···直至 Pj和模式或某个字符匹配成功，或者找不到左子串 =右子串，则 next[j+1]=1 (4-12)
求模式串 next函数值的算法第四章 串第 49页
求模式串 next函数值的算法
get_next(SString t; int next[] )
{ //求模式串 t的 next函数值并存入数组 next
j=1; k=0; next[1] = 0; //初始化
while( j < length(t))
if((k==0)||(t[j]==t[k]))
{j++; k++; next[j] = k }
else k = next[k];
} //get_next 算法 4.6
第四章 串第 50页
求模式串 next函数值的算法例 8,求模式串 t=`abcaababc`的 next函数值（利用算法 4.6）
1) j=1,k=0,next[1]=0
2) ∵ k=0,∴ j=2,k=1,next[2]=k=1
3) ∵ k ≠0,p2≠p1,∴ k=next[k] =next[1]=0
4) ∵ k=0,∴ j=3,k=1,next[3]=k=1
5) ∵ k ≠ 0,p3≠p1,∴ k=next[1]=0
6) ∵ k=0,∴ j=4,k=1,next[4]=k=1
7) ∵ p4=p1,∴ j=5,k=2,next[5]=k=2
8) ∵ k≠0,p5≠p2,∴ k=next[2]=1
9) ∵ p5=p1,∴ j=6,k=2,next[6]=k=2
10) ∵ p6=p2,∴ j=7,k=3,next[7]=k=3
11) ∵ k≠0,p7≠p3,∴ k=next[3]=1
12) ∵ p7=p1,∴ j=8,k=2,next[8]=k=2
13) ∵ p8=p2,∴ j=9,k=3,next[9]=k=3
j=9跳出 WHILE循环，算法 4.6执行完毕。
j=1; k=0; next[1] = 0; //初始化
while( j < length(t))
if((k==0)||(t[j]==t[k]))
{j++; k++; next[j] = k }
else k = next[k];
第四章 串第 51页示例 9 填写以下模式串的 next函数值
1,t=`aaaab`
j 1 2 3 4 5
模 式 a a a a b
next[j] 0 1 2 3 4
模式串 t=`abcaababc`的 next函数值
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 1 2 2 3 2 3
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 1 2 2 3 2 3
1+1 1+1
第四章 串第 52页示例 10 设 S=`aaabaaaab`,P=`aaaab`,写出模式串 `aaaab`的 next函数值，并给出模式匹配过程。
模式串 `aaaab`的 next函数值第一趟匹配 aaabaaaab
aaaa next[4]=3
第二趟匹配 aaabaaaab
aaa next[3]=2
第三趟匹配 aaabaaaab
aa next[2]=1
第四趟匹配 aaabaaaab
a next[1]=0
第五趟匹配 aaabaaaab 匹配，
aaaab 返回定位序号 5
模式匹配过程
↑
↓
↓
↓
↓
↓ ↓
↑
↑
↑
↑
j 1 2 3 4 5
模 式 a a a a b
next[j] 0 1 2 3 4
求模式串 next函数值的 修正 算法第四章 串第 53页分析,第二、三、四趟匹配实无必要进行，宜将模式一次向右滑动 4个字符位置，直接进行 i=5与 j=1的字符比较。
按原先定义，当 Si≠Pj时,Si应与 Pk比较，而 k=next[j]
。 今若 Pj=Pk，则当 Si≠Pj时,Si不再和 Pk进行比较，而直接和 Pnext[k]进行比较，换言之，此时的 next[j]应和 next[k]
相等。故需重新设计计算 next函数的修正值的算法，取名
nextval，以替代 next.但原先 KMP算法仍保持不变，仅需将 next改为 nextval,
求模式串 next函数值的 修正 算法第四章 串第 54页再看一下计算 next函数值的算法
get_next( string t,int next[])
{ //求模式串 t的 next函数值并存入数组 next
j=1; k=0; next[1]=0; //初始化
while( j<length(t))
if((k==0) || (t[j]==t[k]))
{ j++; k++; next[j]=k }
else k = next[k];
} //get_next
算 法 4.6
求模式串 next函数值的 修正 算法第四章 串第 55页计算 next函数修正值的算法
get_nextVal( string t,int nextval[] )
{ //求模式串 t的 next函数修正值
j=1; k=0; nextval[1]=0; //初始化
while( j < length(t))
if((k==0) || (t[j]==t[k]))
{ j++; k++;
if( t[j]≠t[k] ) nextval[j] = k;
else nextval[j] = nextval[k]
}
else k = nextval[k];
} //get_nextval 算法 4.7
算法分析：时间复杂度 O(m).
求模式串 next函数值的 修正 算法第四章 串第 56页示例 11 求模式串 t=`aaaab`的 next函数修正值。
走一下程序
1) j=1,k=0,nextval[1]=0
2) ∵ k=0,∴ j=2,k=1,
∵ p2=p1,∴ nextval[2]=nextval[1]=0
3) ∵ p2=p1,∴ j=3,k=2,
∵ p3=p2,∴ nextval[3]=nextval[2]=0
4) ∵ p3=p2,∴ j=4,k=3,
∵ p4=p3,∴ nextval[4]=nextval[3]=0
5) ∵ p4=p3,∴ j=5,k=4,
∵ p5≠p4,∴ nextval[5]=4
j 1 2 3 4 5
模 式 a a a a b
next[j] 0 1 2 3 4
nextval[j] 0 0 0 0 4
j 1 2 3 4 5
模 式 a a a a b
next[j] 0 1 2 3 4
nextval[j]
求模式串 next函数值的 修正 算法
while( j < length(t))
if((k==0) || (t[j]==t[k]))
{ j++; k++;
if( t[j]≠t[k] )
nextval[j] = k;
else
nextval[j] = nextval[k]
}
else k = nextval[k];
第四章 串第 57页性质 1 next[j]为整数，且 0≤next[j]<j.
性质 2 next[1]=0.
性质 3 对于 j>1，有
其它情况若有
,1
)1,1,()1,1,(,][ kkjpS u b s t rkpS u b s t rkjn ext
性质 4 如果满足性质 3中的 k有多个取值，则应取其中最大的 k值，以保不丢失匹配成功的机会又,nextval函数的性质：除以上性质 1至性质 4外，还有性质 5 令 nextval[j]=k，则若 pj=pk，有 nextval[j]=nextval[k].
Next函数的性质第四章 串第 58页示例 12 设 s=`aabcbabcaabcaababc`,t=`abcaababc`
求模式串 t的 next函数值与 nextval函数值，并分别写出按 next函数值及按 nextval函数值的模式匹配过程。
[分析 ] 先使用算法 4.6（过程 get_next)和算法 4.7
（过程 get_nextval）分别求得模式串 t=`abcaababc`的 next函数值和 nextval函数值，然后可用经验方法验证之。
示例
1）求 模式串 t=`abcaababc`的 next函数值
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 1 2 2 3 2 3
1+1 1+1
第四章 串第 59页
2）求模式串 t=`abcaababc`的 nextval函数值（利用算法 4.7）
1) j=1,k=0,nextval[1]=0
2) ∵ k=0,∴ j=2,k=1;
∵ p2≠p1,∴ nextval[2]=k=1
3) ∵ k≠0,p2≠p1,∴ k=nextval[1]=0
4) ∵ k=0,∴ j=3,k=1;
∵ p3≠p1,∴ nextval[3]=k=1
5) ∵ k≠0,p3≠p1,∴ k=nextval[1]=0
6) ∵ k=0,∴ j=4,k=1;
∵ p4≠p1,∴ nextval[4]=nextval[1]=0
7) ∵ p4=p1,∴ j=5,k=2;
∵ p5≠p2,∴ nextval[5]=k=2
8) ∵ k≠0,p5≠p2,∴ k=nextval[2]=1
9) ∵ p5=p1,∴ j=6,k=2;
∵ p6=p2,∴ nextval[6]=nextval[2]=1
10) ∵ p6=p2,∴ j=7,k=3;
∵ p7≠p3,∴ nextval[7]=k=3
while( j<length(t))
if(k==0)||(t[j]==t[k])
{ j++; k++;
if(t[j]≠t[k] )
nextval[j]=k
else
nextval[j]=nextval[k]
}
else k=nextval[k];
第四章 串第 60页
11) ∵ k≠0,p7≠p3,∴ k=nextval[3]=1
12) ∵ p7=p1,∴ j=8,k=2;
∵ p8=p2,∴ nextval[8]=nextval[2]=1
13) ∵ p8=p2,∴ j=9,k=3;
∵ p9=p3,∴ nextval[9]= nextval[3]=1
j=9 跳出 WHILE循环，算法 4.7执行完毕。
模式串 t=`abcaababc`的 next函数值
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 0 2 1 3 1 1
验证（“两步”法：先写出 next函数值，再修改局部值）
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 1 2 2 3 2 3
nextval[j] 0 1 1 1 2 2 3 2 3 （照抄）
0 1 1 1 （修改）
第四章 串第 61页
1,朴素的模式匹配算法（ BF算法）的时间复杂度为
O(n*m).但在一般情况下，其实际的执行时间近似于 O(n+m)，因此至今仍被采用。
2,改进的模式匹配算法（ KMP算法）的时间复杂度为 O(n+m).
3,KMP算法在 n>>m且模式与主串（目标串）之间存在许多部分匹配时，较 BF算法显得 更为有效。
4,KMP算法的最大特点是指示主串的 指针不需要回溯,在整个匹配过程中，对主串仅需从头至尾扫描一遍。 这对处理从外设输入的庞大文件很是有效，
可以边读入边匹配，而无需回头重读。
模式匹配小结第四章 串第 62页
5,KMP算法特别适合于模式被反复使用的场合。
6,KMP算法的设计方式具有代表性。
7.在 KMP算法中所用到的诸 next函数值可由求模式串的 next函数算法获得。
8,Next函数仅与模式串有关，而与主串无关。
9,可以用求 next函数修正值的算法来代替求
next函数值的算法，而 KMP算法无需作其他改动。
模式匹配小结第四章 串第 63页文本编辑把程序看成是一个字符串 —— 文本串。页是文本串的子串，行是页的子串。
100 PROCEDURE P;
110 VAR i,j,k:real;
120 BEGIN
130 read(i,j );
140 IF i>j THEN k:=j
150 ELSE k:=i
160 END;
串操作应用举例第四章 串第 64页文本格式示例
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
P R O C E D U R E P ; V A R i,
j,k,r e a l ; B E G I N
r e a d ( i,j ) ; I F i >
j T H E N k,= j
E L S E k,= i E N D ;
201
221
241
261
281
文 本 串 行 表
行 号 起 始 地 址 长 度
100 201 13
110 214 17
120 231 8
130 239 14
140 253 20
150 237 20
160 239 7
串操作应用举例第四章 串第 65页第四章 串 小结
● 内容提要串的逻辑结构及基本操作；串的定长静态顺序存储结构和动态
（链式、堆）存储结构；串基本操作的实现；
模式匹配（求子串位置的定位操作）的 BF算法
,KMP算法，以及求模式串 next录取数值的算法及修正算法
● 学习要点熟悉串的有关概念，
串和线性表的关系；掌握串的各种存储结构，比较它们各自的优缺点；熟悉串的各种基本操作，并能利用这些基本操作实现串的其它操作；掌握模式匹配的 BF算法,KMP算法以及求模式串的 next函数值及 nextval函数值 的方法及技巧。
,数据结构,
第四章 串第 2页主要内容
1,串的逻辑结构
2,串的基本操作
3,串的链式存储结构
4,串的堆存出结构
5,串的顺序存储结构
6,静态结构存储串时的操作第四章 串第 3页主要内容
静态结构存储串时的操作（ Index函数）
朴素的模式匹配算法（ BF算法）
改进的模式匹配算法（ KMP算法）
求模式串 next函数值的算法
求模式串 next函数值的修正算法
next函数的性质
示例与模式匹配
7.模式匹配（ 重点 ）
第四章 串第 4页第四章 串串（又称字符串）是一种特殊的 线性表,它的每个结点仅由一个字符组成
。
本章将讨论串的有关概念、结构、
存储方法和串的基本运算及其实现。
第四章 串第 5页定义,串（ String）是零个或多个字符组成的有限序列。
一般记为,S=‘a1a2···a n’ (n≥0).
术语
1） 串名,S.
2） 串值,'a1a2···a n',ai(1≤i≤n).
3） 串的长度,串中所包含的字符个数，如串
'abcde'的长度为 5,
串的逻辑结构第四章 串第 6页
4） 空串,长度为 0(n=0)的串，它不包含任何字符，记作 S=''(或 S=φ).
5） 空格串,由空格符 (ASCII值 32)组成的串，
如 S=‘’.注意 S= '?'与 S=''不同，前者是长度为 1的非空串，它含有一个空格字符，而后者是长度为 0的空串。
6） 子串,串中任意个连续的字符组成的子序列
。比如 'abcde'中的 'bcd'.
串的逻辑结构第四章 串第 7页用二元组的形式来定义串,串是一个二元组,
string = ( D,R )
其中
D={ai|ai∈ 字符集,i=1,2,···,n,n≥0}
R={N}
有序偶的集合 N={<ai-1,ai>| ai-1,ai ∈ D,i=2,3,···n}
故串的逻辑结构和线性表极为相似。区别仅在 D
的定义上。 线性表的数据对象可以是 任意数据类型,
而串的数据对象是 字符集 。
串是几种最简单的数据结构之一。
串的逻辑结构第四章 串第 8页串虽然是一种特殊的线性表，但由于存储结构有所不同，故其基本操作也不同。
1、基本操作子集不同，比如串包含有联接、求子串等操作
2、操作对象不同，线性表的操作通常以 数据元素或结点 为操作对象，而串的操作主要以串的 整体 为操作对象。
1）赋值操作
Assign(s,t) s为串名,t为字符串变量。
Create(s,ss) s为串名,ss为字符序列。
2）判等函数
Equal(s,t) 返回布尔值 true或 false.s,t可为非空串或空串。
3）求串长函数
Length(s) 返回串 s字符的个数。
4）联接函数
Concat(s,t) 返回由串 s,t相联接而成的新串。联接运算不满足交换律，但满足结合律。
串的基本操作第四章 串第 9页
5） 求子串函数
Substr(S,start,len) 返回从串 S中第 start个字符起，长度为
len的字符序列。
要求 1≤start≤Length(s)+1,
0≤len≤ Length(s)-start+1.
6）定位函数
Index(s,t)
返回串 t在串 s中第一次出现时的串首位置，若未出现，则返回值 0，要求 t不能是空串。
7）置换操作
Replace(s,t,v)
以串 v替换所有在串 s中出现的和非空串 t相等的子串。
串的基本操作第四章 串第 10页
串的基本操作
8）插入（前插）操作
Insert(s,pos,t)
在串 s的第 pos个字符之前插入串 t,要求 1≤pos≤Length(s)+1。
注,Insert(S,Length(s)+1,t) 与 Concat(s,t)功能相同，
即当 pos= Length(s)+1时,t将插入至 s的尾部之后。
9）删除操作
Delete(s,pos,len)
从串 s中删去从第 pos个字符起，长度为 len的子串。要求
1≤pos≤Length(s)，
且 1≤len≤Length(s)-pos+1。
说明：可将 1)至 5)定义为串的基本操作,6)至 9)可由基本操作加以实现。
第四章 串第 11页示例 1 用串的基本操作 (1)至 (5)实现定位函数 Index(s,t)。
int Index( string s,string t )
/*若串 s中存在和 t相等的子串，则返回第一个子串在主串中的位置，否则返回零 */
{ n = Length(s); m = Length(t); i = 1; //m不等于 0
while( i ≤ n-m+1 )
if( Equal( Substr( s,i,m ),t ))
return i;
else i++;
return 0;
} //index
串的基本操作第四章 串第 12页
C中预定义字符串标准函数和标准过程字符串标准函数函数名 意 义 结果类型
strcat 连接字符串序列 char *
strcpy 复制一个字符串 char *
strlen 返回串的动态长度 int
还有,strcmp,strcmpi,strrchr,… …
参见：
String.h
串的基本操作第四章 串第 13页用线性链表的方式存储串值结点大小问题
串的 链式 存储结构
D A T A S ^
head
1）结点大小等于 1，即一个结点存放一个字符优点,便于实现插入、删除等操作缺点,浪费存储空间，存储利用率最多 1/2
DA T A S TR UCTU RES ^
head
2）结点大小等于 4，即一个结点存放 4个字符优点,存储效率较高缺点,实现插入、删除等操作较复杂
^H
第四章 串第 14页用块链结构存储串值为便于进行串的操作，当以链表存储串值时,给出头、尾指针，加当前串的长度 。称如此定义的 串存储结构为块链结构
。
设尾指针的目的是为了便于进行联接操作。
块链结构的说明
#define CHUNK_SIZE 1000 //用户定义的结点大小
typedef struct {
char ch[CHUNK_SIZE]; //块大小
chunk *next; //指针
} chunk;
typedef struct {
chunk *head,*tail; //头、尾指针
int length; //长度
} LString;
LString clst;
串的 链式 存储结构第四章 串第 15页
clst 15
DA T A S TR UCTU RES # ^
头 尾 长度块链结构示意图
串的 链式 存储结构用块链结构存储串值串值所占存储空间存储密度 = —————————— < 1
实际分配的存储空间这种存储方式对某些操作比较方便，总的来说仍较复杂。
第四章 串第 16页特点,每个串的串值各存储在一组 地址连续的存储 单元中，但它们的存储地址是在程序执行过程中 动态分配 而得。
typedef struct{
char *ch;
int length;
}HString;
使用时必须分配 (malloc)和回收 (free)内存。
串的 堆 存储结构用堆结构存储串值第四章 串第 17页
21
15
··· A STRING OF LENGTH 21F
··· DATA STRUCTURES ···
Heap
s1
串的动态分配存储结构示意图起始地址起始地址
free
length ch
Free是指尚未分配内存地址
串的 堆 存储结构
s2
定义
HString s1
HString s2
第四章 串第 18页
1、赋值操作 Assign(s,t)
Status Assign( HString &t; char *s )
{ //将 s串的值赋给 t串
if( s.ch ) free( t.ch );
for( i=0,c=s; c; i++,c++ ); //求 s的长度
if( !i ){ t.ch = NULL; t.length = 0;}
else{
if(!(t.ch=(char*)malloc(i*sizeof(char))))
return OVERFLOW;
t.ch[0..i-1] = s[0..i-1];
t.length = i;
}
return OK;
}
算 法 4.9
串的 堆 存储结构第四章 串第 19页
2、联接运算 Concat
Status Concat( HString &t,HString s1,HString s2 )
{ //连接 s1,s2到 t中
if( t.ch ) free( t.ch ); //释放原空间
if(!(t.ch=(char*)malloc(s1.length+s2.length)*sizeof(char))))
return OVERFLOW; //分配空间
t.ch[0..s1.length-1] = s1.ch[0..s1.length-1]; //处理 s1
t.length = s1.length + s2.length; //长度
t.ch[s1.length..t.length-1] = s2.ch[0..s2.length-1]; //s2
}
串的 堆 存储结构第四章 串第 20页
3、求子串函数 Substr
Status SubStr( HString &sub,HString s,int pos,int len )
{ //从 s的 pos位置取 len长的子串，由 sub返回
if(pos<1||pos>s.length||len<0||len>s.length-pos+1)
return ERROR; //非法
if( sub.ch ) free( sub.ch ); //释放原有空间
if( !len ){ sub.ch = NULL; sub.length = 0 } //空串
else{
sub.ch = (char*)malloc(len*sizeof(char)); //分配空间
sub.ch[0..len-1] = s[pos-1..pos+len-2]; //取子串
sub.length = len;
}
return OK;
}
串的 堆 存储结构第四章 串第 21页
用一组 地址连续 的存储单元来存储串的字符序列。
每个字符占用一个 字节（ Byte） 。串中相邻的字符顺序地存放在相邻的字节中。
D A T A S T R U C T U R E S
l+1 l+2l l+15......
串的定长顺序存储结构定长顺序存储结构串定义：
#define maxlen 255 //允许最大的长度
typedef unsigned char String[maxlen+1]; //下标 0存放长度实现,串的联接函数,求子串的函数,求子串位置的定位函数第四章 串第 22页其中 L,s,t是 String；
[分析 ] 相当于求 L=s+t，若 s与 t连接后的串值长度超过 maxlen，则超过部分将被截断。 运算结果有三种可能情况。
1) length(s) + length(t) ≤ maxlen
Length(s)
s.ch
Length(t)
t.ch
定长顺序存储时的操作
1、串的联接函数 Concat(L,s,t)
L,ch
maxlenLength(L)
可得到串 L的正确结果第四章 串第 23页
Length(s)
s.ch
Length(t)
t.ch
定长顺序存储时的操作
2) length(s) + length(t) > maxlen而 length(s) < maxlen
需将 t的一部分截断，所得串 L中包含 s的全部与 t的一个子串
L,ch
maxlenLength(L)
t中被截去的字符序列第四章 串第 24页
Length(s)
s.ch
Length(t)
t.ch
L.ch
maxlenLength(L) t串被全部截去
3) length(s)=maxlen
得到的串 L是 s的串。
定长顺序存储时的操作第四章 串第 25页
Status Concat( string &L,string s,string t )
{ /*返回 s和 t联接的结果,s和 t的值不变。 */
switch{
case length(s) + length(t)≤maxlen,//正常联接
L[1.,length(s)] = s[1.,length(s)];
L[length(s)+1.,length(s)+ length(t)] = t[1.,length(t)];
L[0] = s[0] + t[0];
overflow = false;
case length(s)<maxlen://串 t截尾
overflow = true;
L[1.,length(s)] = s[1.,length(s)];
L[length(s)+1..maxlen] = t[1..maxlen - length(s)];
L[0] = maxlen;
default,//串中只含 s
overflow = true; L[1..maxlen] = s[1..maxlen]; L[0] = maxlen;
}; //switch
return overflow;
} // 算 法 4.2
定长顺序存储时的操作第四章 串第 26页
[分析 ] 复制字符序列，若 1≤start≤length(s)+1且 0≤len≤length(s)-
start+1，则将串 s从第 start个字符起长度为 len的子串赋给串 sub,并返回函数值 true，否则返回函数值 false，而 sub无确定值，为非法串。
Status Substr( string &sub,string s,int start,int len )
{ if((1≤start && start ≤length(s)+1) &&
(0≤len && len ≤length(s)-start+1))
{ sub.ch[1..len] = s.ch[start..start+len-1];
sub[0] = len;
return true;
}
return false;
} //substr 算 法 4.3
定长顺序存储时的操作
2、求子串的函数 Substr(sub,s,start,len).
第四章 串第 27页设有两个串
s = 's1s2···sn'
p = 'p1p2···pm' (0<m≤n)
称主串 S为目标（串）,子串 p为模式（串） 。
串的 模式匹配,在目标 S中寻找模式为 p的子串的过程,
串模式匹配的结果：
（ 1） 成功,Index(S,p) > 0
（ 2） 失败,Index(S,p) == 0
其中 Index返回第一个模式为 p的子串在主串 s中的位置。
定长顺序存储时的操作
3、求子串位置的定位函数 Index(s,p)
模式匹配算法，其中 p为模式第四章 串第 28页
定长顺序存储时的操作
3、求子串位置的定位函数 Index(s,p)
使用串的基本操作 (如 Equal,Length,Substr等 )实现求子串位置的定位函数 Index(s,p)的算法：
int Index( string s,string p )
{ n = Length(S);
m = Length(p);
i = 1;
while( i ≤ n – m + 1 )
if( Equal(Substr(S,i,m),p))
return i;
else i++;
return 0;
} //index
第四章 串第 29页根据上面算法的基本思想，可以写出一种不依赖于其他串基本操作的模式匹配算法 —— 朴素的模式匹配算法（
Brute-Force算法）。
BF算法的基本思想,用 p中字符依次与 s中字符比较
，以指示器 i,j分别指向 s,p。 ① 初始时令 i=1,j=1。 ② 若有
s[i]==p[j]，则令 i,j分别加 1，继续比较。当
j==(length(p)+1)，则匹配成功，返回相应的位置值。 ③
若在某时刻有 s[i]≠p[j]，则 i回退到 i-(j-1)+1=i-j+2处，令 j=1
，再进行逐个字符比较。 ④ 若直到 i>length(s)时尚未匹配成功，则表示匹配失败,返回值 0。
定长顺序存储时的操作
3、求子串位置的定位函数 Index(s,p)
朴素的模式匹配算法（ BF算法）
第四章 串第 30页
定长顺序存储时的操作
3、求子串位置的定位函数 Index(s,p)
朴素的模式匹配算法（ BF算法）
int Index_BF( string s,string p )
{ //求模式串 t在主串 s中位置的定位函数
i=1;j=1; //指针初始化
while( i≤length(s) && j≤length(p))
if( s[i] == p[j] )
{ i++； j++ } //继续比较后继字符
else
{ i = i-j+2； j = 1 }; //指针后退重新开始匹配
if( j > length(p))
return( i – length(p)); //匹配成功，返回定位序号
else
return(0); //匹配失败，返回值 0
}; //index_BF 算 法 4.4
第四章 串第 31页示例 1 设 s='ababcabcacbab',p='abcac'，求函数
Index_BF(s,p)的值。
算法 Index_BF的匹配过程如下：
第一趟匹配 ababcabcacbab { j 返回至 1,i返回至 i-j+2=3-3+2=2}
abc? j=3
第二趟匹配 ababcabcacbab { j 返回至 1,i返回至 i-j+2=2-1+2=3}
a? j=1
第三趟匹配 ababcabcacbab { j返回至 1,i 返回至 i-j+2=7-5+2=4}
abcac? j=5
↓i=3
↓i=2
↓i=7
朴素的模式匹配算法（ BF算法）
第四章 串第 32页第四趟匹配 ababcabcacbab {j返回至 1,i返回至 i-j+2=4-1+2=5}
a? j=1
第五趟匹配 ababcabcacbab {j返回至 1,i返回至 i-j+2=5-1+2=6}
a? j=1
第六趟匹配 ababcabcacbab {j>length(t)(6>5)匹配成功，返回 }
定位 abcac? j=6
算法的匹配过程
↓i=4
↓i=5
↓i=11
朴素的模式匹配算法（ BF算法）
第四章 串第 33页算法复杂性分析
● 一般情况,设
S='A STRING SEARCHING EXAMPLE CONSISTING'
+ 'OF SIMPLE TEXT' (n=52)
p='STING' (m=5)
BF算法执行 while语句中循环体的次数（即进行单个字符比较的次数）为
(index+length(p)-1)+4
=(33+5-1)+4
=41.
即除了主串中下划线的 4个字符均比较了 2次以外，其他字符均只和模式进行了 1次比较。
时间复杂度为 O(n+m)，这里 n是 s的长度,m是 p的长度,
Index=33
↓
第四章 串第 34页
● 特殊情况,设
S='OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO'
+’OOOOOOOOOOOO1’ (n=53)
p=’OOOOOOO1’ (m=8)
BF算法执行 while语句中循环体的次数（即进行单个字符比较的次数）为
index× m=46× 8=368.
故 BF算法在最坏情况下的时间复杂度为 O(n× m)，这里 n
是 s的长度,m是 p的长度,
算法效率差的原因：指针 i的 多次回溯 。而这些回溯并非是必须的。
Index=46
算法复杂性分析第四章 串第 35页示例 4 设 s=`abbaba`,p=`aba`,则 BF算法的匹配过程如下第一趟匹配 abbaba j返至 1,i返至 i-j+2=3-3+2=2
1) aba
第二趟匹配 abbaba j返至 1,i返至 i-j+2=2-1+2=3
2) a
第三趟匹配 abbaba j返至 1,i返至 i-j+2=3-1+2=4
3) a
第四趟匹配 abbaba j>length(p)(4>3)，匹配成功，返回定位
4) aba 序号 i-length(p)=7-3=4
↓i=3
↓i=2
↓i=3
↓i=7
↑j=3
↑j=1
↑j=1
↑j=4
改进的模式匹配算法（ KMP算法）
问题,①是否有不必要的回溯，即有没有冗余信息？
②是否可以不回溯？
③能否每次将模式向右”滑动,1位改成”滑动“尽可能的一段距离后，继续进行比较？
第四章 串第 36页讨论①
由 1) 知 p1=s1,p2=s2,p3≠s3
知 p1≠p2，故 p1≠s2，所以将 p右移 1位后的比较一定不等，即步骤 2) 是不必要的。
再由 p1=p3，可以推出 p1≠s3，所以将 p再右移 1位后的比较也一定不等，即步骤 3)亦是不必要的。
结论,在朴素算法中未利用部分有用信息。在此例中，由步骤
1) 便可直接将 p右移 3位，跳至步骤 4)，从 p1和 s4开始继续比较。
第一趟匹配 abbaba 将 t右移 3位
aba
第二趟匹配 abbaba 匹配成功
aba
↓i=3
↓i=7
↑j=3
↑j=4
改进的模式匹配算法（ KMP算法）
第四章 串第 37页讨论②
不回溯是可能的,因为模式不可能全在 si之前，模式只可能在 si 前后或全在 si 之后。故可另辟新路,i不回溯，而令模式串向右“滑动”。
讨论③
当某个字符比较不相等时,模式 p究竟应向右“滑动”至哪个位置再继续比较？或者说 模式 p要移动多少位？（在朴素算法中 p每次右移 1位）
KMP算法 （ D.E.Knuth,J.H.Morris,V.R.Pratt）的改进在于：
每当一趟匹配过程中出现字符不等时，不需回溯 i指针，而是 利用 已经得到的,部分匹配,的结果，将模式向右,滑动,尽可能远的一段距离后，继续进行匹配比较 。
改进的模式匹配算法（ KMP算法）
第四章 串第 38页再看示例 1
s=`ababcabcacbab`
p=`abcac`
第一趟匹配 ababcabcacbab 仅需要将模式向右移动两个字符的
abc 位置继续进行 i=3,j=1时的字符比较第二趟匹配 ababcabcacbab 在 i=4和 j=1,i=5和 j=1和 i=6和 j=1这
abcac 三次比较都是不必进行的第三趟匹配 ababcabcacbab 匹配成功！
(a)bcac
图 4.4 改进算法的匹配过程示例在整个匹配的过程中,i指针没有回溯。
↓i=3
↓i=3
↑j=3
↑j=1
↑j=2
↓i=7
↑j=5
↑i=7 ↑i=11
↑j=6 图 4.4 参见教材 p.80
第四章 串第 39页三条规则
1）若模式中第一个字符就与 si不同（ p1≠si），则将 si+1与 p1继续比较（或 si与 p0相比较）；否则
2）若模式中有 左子串 =右子串,即 ` p1··· pk-1`=` pj-k+1··· pj-1`，
则将 si与 pk继续比较；
3）若模式中无 左子串 =右子串,则令 si与 p1继续比较。
再看示例 4，运用上述诸规则 s=`abbaba`,p=`aba`
第一趟匹配 abbaba 规则 3）,si(i=3)与 p1继续比较
aba
第二趟匹配 abbaba 规则 1）,si+1(i=3)与 p1继续比较
a
第三趟匹配 abbaba 匹配，得序号 i-length(p)=7-3=4
aba
↓i=3
↑j=4
↓i=7
↑j=3
↑j=1
改进的模式匹配算法（ KMP算法）
第四章 串第 40页按三条规则再看示例 1
S=`ababcabcacbab`
p=`abcac`
第一趟匹配 ababcabcacbab
abc 规则 3）,si(i=3)与 p1继续比较第二趟匹配 ababcabcacbab
abcac 规则 2）,si(i=7)与 p2继续比较第三趟匹配 ababca bcacbab
(a)bcac 匹配成功！
↓i=3
↑j=3
↓i=7
↓i=11
↑j=5
↑j=6
第四章 串第 41页设主串 s=`s1s2···sn`,
模式串 p=`p1p2···pm` (0<m≤n).
问题：当匹配过程中产生失配（即 si≠pj)时,si（ i指针不回溯）应与模式中哪个字符再继续比较，即模式串可“向右滑动”多远距离？
设此时 si应与 pk(k<j)继续比较
s1 s2 · · · si · · · sn
··· pk ··· pj
则有
S1 S2 · · · Si-k+1 Si-k+2 · · · Si-1 Si · · · Sn
p1p2 · · · pk-1pk · · · pj
`p1p2 ··· pk-1`= `Si-k+1 Si-k+2 ··· Si-1` (4-2)
K-1个
K-1个
求模式串的 next函数第四章 串第 42页另外，由于 si≠pj，则已经得到的“部分匹配”结果是
S1 S2 · · · Si-j+1 Si-j+2 · · · Si-k+1 Si-k+2 · · · Si-1 Si · · ·
P1 P2 · · · Pj-k+1 Pj-k+2 · · · Pj-1 Pj
其中紧靠 si（或 pj）的 k-1个对应字符都相等
`Pj-k+1 Pj-k+2 · · · pj-1`= `Si-k+1 Si-k+2 · · · Si-1 ` (4-3)
由 (4-2),(4-3)，可推得
`P1P2 · · · Pk-1`=Pj-k+1 Pj-k+2 · · · Pj-1` (4-4)
反之，只要满足 (4-4)式，则 Si可与 Pk继续比较。但请注意，应当寻找最大可能的左子串 =右子串,以确定最大可能的 k.
K-1个
j-1个
求模式串的 next函数第四章 串第 43页示例 6 设模式串 P=`abaabcac`，则可得如下之 next函数值
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
注 1.必有 next[j]<j.
注 2,Next[j]（即 k）值只取决于模式串 p本身，而与目标串 S无关系令 next[j]=k,next[j]表明当模式中第 j个字符与主串中相应字符
“失配”时，在模式中需重新和主串中该字符进行比较的字符的 位置 。这是一个函数关系，称作 模式串的 next函数。 由前述的讨论知
：
)(,1
)` } (```1{
),(1,0
][
1
1111
111
继续比较与其它情况继续比较与且继续比较与即与则令就不匹配与时当
PS
PSPPPPjkkM a x
PSPSPSj
jn e x t
i
kijkjk
oiii
第四章 串第 44页示例 7 利用模式的 next函数进行匹配的过程
S=`acabaabaabcacaabc`
P=`abaabcac`
第一趟匹配 acabaaba···
ab next[2]=1
第二趟匹配 acabaaba···
a next[1]=0
第三趟匹配 acabaabaab···
abaabc next[6]=3
第四趟匹配 acabaabaabcacaabc···
abaabcac
匹配，得序号 index(s,p)=i-length(p)=14-8=6.
↓i=2
↑j=2
↑j=1
↑j=1 ↑j=6
↑j=3 ↑j=9
↓i=2
↓i=3 ↓i=8
↓i=8 ↓i=14
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
求模式串的 next函数第四章 串第 45页基于 next函数的匹配移位规则：
设 i,j分别指示主串和模式串中正待比较的字符，
初值 i=1,j=1.
1) 若 Si=Pi，则 i,j分别加 1，返至 1)；
2) 若 Si≠Pi，则 j退到 next[j]位置再比较，
a.当 j>0，则返至 1)；
b.当 j=0（即模式的第一个字符“失配”），则令
i加
1,j加 1（即 j=1），返至 1)；
如此继续，直至 匹配成功 (j>length(t))，并进而获得定位序号，或者 匹配失败 (i>length(s)而 j≤length(t)).
求模式串的 next函数第四章 串第 46页
KMP算法的实现
int index_KMP( SString s,SString t )
{ //利用模式串的 next函数求模式串 t在主串 S中位置的 KMP算法
i = 1; j = 1; //指针初始化
while((i≤length(s)) && (j≤length(t)))
if((j==0)||(s[i]==t[j]))
{i++;j++} //继续下一对字符的比较
else j = next[j]; //模式串向右滑动
if( j > length(t))
return(i-length(t)); //匹配成功
else
return(0);
} //index_KMP 算 法 4.5
第四章 串第 47页注 1,KMP算法是在已知模式串的 next函数值的基础上执行的，故其前提是假定已有求得模式串的 next函数值的算法。
注 2,算法中 j=0表明 Si与 P1就不匹配，故令 i加 1,j
加 1(0+1=1)，即令 Si+1与 P1继续比较。
注 3,算法分析（时间复杂度）,(1)该算法执行过程中 i只增不减,由 i初值为 1，循环过程中保持 i≤n，所以循环体中 i++最多执行 n次； （ 2） 另外 j的初值为 1，
而循环体中保持 j>0,由于 next[j]<j，所以 j=next[j]的 最多执行次数也不超过 n,故上述算法的时间复杂度为 O(n)
。
第四章 串第 48页算法思想可以从分析其定义出发，用递推的方法求得 next函数。
1)由定义知
next[1]=0 (4-6)
2)设 next[j]=k(1<k<j，最大的 k)，
`P1···P k-1`=`Pj-k+1···P j-1` (4-7)
今求 next[j+1]?
a,若 Pk=Pj，则由 (4-7)而得
`P1···P k`=`Pj-k+1···P j` (4-8)
即 next[j+1]=k+1=next[j]+1 (4-9)
b,若 Pk≠Pj,则
`P1···P k` ≠ `Pj-k+1···P j`
而将 `Pj-k+1···P j`看作主串。 Pj应与 Pnext[k]继续比较。记 next[k]=k`,若 Pj=Pk`，则有
`P1···P k``=`Pj-k`+1···P j`(1<k`<k<j) (4-10)
即 next[j+1]=k`+1，亦即
next[j+1]=next[k]+1 (4-11)
而若 Pj≠Pk`，则将模式继续向右滑动,Pj应与 Pnext[k`]继续比较。 ··· ···直至 Pj和模式或某个字符匹配成功，或者找不到左子串 =右子串，则 next[j+1]=1 (4-12)
求模式串 next函数值的算法第四章 串第 49页
求模式串 next函数值的算法
get_next(SString t; int next[] )
{ //求模式串 t的 next函数值并存入数组 next
j=1; k=0; next[1] = 0; //初始化
while( j < length(t))
if((k==0)||(t[j]==t[k]))
{j++; k++; next[j] = k }
else k = next[k];
} //get_next 算法 4.6
第四章 串第 50页
求模式串 next函数值的算法例 8,求模式串 t=`abcaababc`的 next函数值（利用算法 4.6）
1) j=1,k=0,next[1]=0
2) ∵ k=0,∴ j=2,k=1,next[2]=k=1
3) ∵ k ≠0,p2≠p1,∴ k=next[k] =next[1]=0
4) ∵ k=0,∴ j=3,k=1,next[3]=k=1
5) ∵ k ≠ 0,p3≠p1,∴ k=next[1]=0
6) ∵ k=0,∴ j=4,k=1,next[4]=k=1
7) ∵ p4=p1,∴ j=5,k=2,next[5]=k=2
8) ∵ k≠0,p5≠p2,∴ k=next[2]=1
9) ∵ p5=p1,∴ j=6,k=2,next[6]=k=2
10) ∵ p6=p2,∴ j=7,k=3,next[7]=k=3
11) ∵ k≠0,p7≠p3,∴ k=next[3]=1
12) ∵ p7=p1,∴ j=8,k=2,next[8]=k=2
13) ∵ p8=p2,∴ j=9,k=3,next[9]=k=3
j=9跳出 WHILE循环，算法 4.6执行完毕。
j=1; k=0; next[1] = 0; //初始化
while( j < length(t))
if((k==0)||(t[j]==t[k]))
{j++; k++; next[j] = k }
else k = next[k];
第四章 串第 51页示例 9 填写以下模式串的 next函数值
1,t=`aaaab`
j 1 2 3 4 5
模 式 a a a a b
next[j] 0 1 2 3 4
模式串 t=`abcaababc`的 next函数值
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 1 2 2 3 2 3
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 1 2 2 3 2 3
1+1 1+1
第四章 串第 52页示例 10 设 S=`aaabaaaab`,P=`aaaab`,写出模式串 `aaaab`的 next函数值，并给出模式匹配过程。
模式串 `aaaab`的 next函数值第一趟匹配 aaabaaaab
aaaa next[4]=3
第二趟匹配 aaabaaaab
aaa next[3]=2
第三趟匹配 aaabaaaab
aa next[2]=1
第四趟匹配 aaabaaaab
a next[1]=0
第五趟匹配 aaabaaaab 匹配，
aaaab 返回定位序号 5
模式匹配过程
↑
↓
↓
↓
↓
↓ ↓
↑
↑
↑
↑
j 1 2 3 4 5
模 式 a a a a b
next[j] 0 1 2 3 4
求模式串 next函数值的 修正 算法第四章 串第 53页分析,第二、三、四趟匹配实无必要进行，宜将模式一次向右滑动 4个字符位置，直接进行 i=5与 j=1的字符比较。
按原先定义，当 Si≠Pj时,Si应与 Pk比较，而 k=next[j]
。 今若 Pj=Pk，则当 Si≠Pj时,Si不再和 Pk进行比较，而直接和 Pnext[k]进行比较，换言之，此时的 next[j]应和 next[k]
相等。故需重新设计计算 next函数的修正值的算法，取名
nextval，以替代 next.但原先 KMP算法仍保持不变，仅需将 next改为 nextval,
求模式串 next函数值的 修正 算法第四章 串第 54页再看一下计算 next函数值的算法
get_next( string t,int next[])
{ //求模式串 t的 next函数值并存入数组 next
j=1; k=0; next[1]=0; //初始化
while( j<length(t))
if((k==0) || (t[j]==t[k]))
{ j++; k++; next[j]=k }
else k = next[k];
} //get_next
算 法 4.6
求模式串 next函数值的 修正 算法第四章 串第 55页计算 next函数修正值的算法
get_nextVal( string t,int nextval[] )
{ //求模式串 t的 next函数修正值
j=1; k=0; nextval[1]=0; //初始化
while( j < length(t))
if((k==0) || (t[j]==t[k]))
{ j++; k++;
if( t[j]≠t[k] ) nextval[j] = k;
else nextval[j] = nextval[k]
}
else k = nextval[k];
} //get_nextval 算法 4.7
算法分析：时间复杂度 O(m).
求模式串 next函数值的 修正 算法第四章 串第 56页示例 11 求模式串 t=`aaaab`的 next函数修正值。
走一下程序
1) j=1,k=0,nextval[1]=0
2) ∵ k=0,∴ j=2,k=1,
∵ p2=p1,∴ nextval[2]=nextval[1]=0
3) ∵ p2=p1,∴ j=3,k=2,
∵ p3=p2,∴ nextval[3]=nextval[2]=0
4) ∵ p3=p2,∴ j=4,k=3,
∵ p4=p3,∴ nextval[4]=nextval[3]=0
5) ∵ p4=p3,∴ j=5,k=4,
∵ p5≠p4,∴ nextval[5]=4
j 1 2 3 4 5
模 式 a a a a b
next[j] 0 1 2 3 4
nextval[j] 0 0 0 0 4
j 1 2 3 4 5
模 式 a a a a b
next[j] 0 1 2 3 4
nextval[j]
求模式串 next函数值的 修正 算法
while( j < length(t))
if((k==0) || (t[j]==t[k]))
{ j++; k++;
if( t[j]≠t[k] )
nextval[j] = k;
else
nextval[j] = nextval[k]
}
else k = nextval[k];
第四章 串第 57页性质 1 next[j]为整数，且 0≤next[j]<j.
性质 2 next[1]=0.
性质 3 对于 j>1，有
其它情况若有
,1
)1,1,()1,1,(,][ kkjpS u b s t rkpS u b s t rkjn ext
性质 4 如果满足性质 3中的 k有多个取值，则应取其中最大的 k值，以保不丢失匹配成功的机会又,nextval函数的性质：除以上性质 1至性质 4外，还有性质 5 令 nextval[j]=k，则若 pj=pk，有 nextval[j]=nextval[k].
Next函数的性质第四章 串第 58页示例 12 设 s=`aabcbabcaabcaababc`,t=`abcaababc`
求模式串 t的 next函数值与 nextval函数值，并分别写出按 next函数值及按 nextval函数值的模式匹配过程。
[分析 ] 先使用算法 4.6（过程 get_next)和算法 4.7
（过程 get_nextval）分别求得模式串 t=`abcaababc`的 next函数值和 nextval函数值，然后可用经验方法验证之。
示例
1）求 模式串 t=`abcaababc`的 next函数值
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 1 2 2 3 2 3
1+1 1+1
第四章 串第 59页
2）求模式串 t=`abcaababc`的 nextval函数值（利用算法 4.7）
1) j=1,k=0,nextval[1]=0
2) ∵ k=0,∴ j=2,k=1;
∵ p2≠p1,∴ nextval[2]=k=1
3) ∵ k≠0,p2≠p1,∴ k=nextval[1]=0
4) ∵ k=0,∴ j=3,k=1;
∵ p3≠p1,∴ nextval[3]=k=1
5) ∵ k≠0,p3≠p1,∴ k=nextval[1]=0
6) ∵ k=0,∴ j=4,k=1;
∵ p4≠p1,∴ nextval[4]=nextval[1]=0
7) ∵ p4=p1,∴ j=5,k=2;
∵ p5≠p2,∴ nextval[5]=k=2
8) ∵ k≠0,p5≠p2,∴ k=nextval[2]=1
9) ∵ p5=p1,∴ j=6,k=2;
∵ p6=p2,∴ nextval[6]=nextval[2]=1
10) ∵ p6=p2,∴ j=7,k=3;
∵ p7≠p3,∴ nextval[7]=k=3
while( j<length(t))
if(k==0)||(t[j]==t[k])
{ j++; k++;
if(t[j]≠t[k] )
nextval[j]=k
else
nextval[j]=nextval[k]
}
else k=nextval[k];
第四章 串第 60页
11) ∵ k≠0,p7≠p3,∴ k=nextval[3]=1
12) ∵ p7=p1,∴ j=8,k=2;
∵ p8=p2,∴ nextval[8]=nextval[2]=1
13) ∵ p8=p2,∴ j=9,k=3;
∵ p9=p3,∴ nextval[9]= nextval[3]=1
j=9 跳出 WHILE循环，算法 4.7执行完毕。
模式串 t=`abcaababc`的 next函数值
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 0 2 1 3 1 1
验证（“两步”法：先写出 next函数值，再修改局部值）
j 1 2 3 4 5 6 7 8 9
模 式 串 a b c a a b a b c
next[j] 0 1 1 1 2 2 3 2 3
nextval[j] 0 1 1 1 2 2 3 2 3 （照抄）
0 1 1 1 （修改）
第四章 串第 61页
1,朴素的模式匹配算法（ BF算法）的时间复杂度为
O(n*m).但在一般情况下，其实际的执行时间近似于 O(n+m)，因此至今仍被采用。
2,改进的模式匹配算法（ KMP算法）的时间复杂度为 O(n+m).
3,KMP算法在 n>>m且模式与主串（目标串）之间存在许多部分匹配时，较 BF算法显得 更为有效。
4,KMP算法的最大特点是指示主串的 指针不需要回溯,在整个匹配过程中，对主串仅需从头至尾扫描一遍。 这对处理从外设输入的庞大文件很是有效，
可以边读入边匹配，而无需回头重读。
模式匹配小结第四章 串第 62页
5,KMP算法特别适合于模式被反复使用的场合。
6,KMP算法的设计方式具有代表性。
7.在 KMP算法中所用到的诸 next函数值可由求模式串的 next函数算法获得。
8,Next函数仅与模式串有关，而与主串无关。
9,可以用求 next函数修正值的算法来代替求
next函数值的算法，而 KMP算法无需作其他改动。
模式匹配小结第四章 串第 63页文本编辑把程序看成是一个字符串 —— 文本串。页是文本串的子串，行是页的子串。
100 PROCEDURE P;
110 VAR i,j,k:real;
120 BEGIN
130 read(i,j );
140 IF i>j THEN k:=j
150 ELSE k:=i
160 END;
串操作应用举例第四章 串第 64页文本格式示例
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
P R O C E D U R E P ; V A R i,
j,k,r e a l ; B E G I N
r e a d ( i,j ) ; I F i >
j T H E N k,= j
E L S E k,= i E N D ;
201
221
241
261
281
文 本 串 行 表
行 号 起 始 地 址 长 度
100 201 13
110 214 17
120 231 8
130 239 14
140 253 20
150 237 20
160 239 7
串操作应用举例第四章 串第 65页第四章 串 小结
● 内容提要串的逻辑结构及基本操作；串的定长静态顺序存储结构和动态
（链式、堆）存储结构；串基本操作的实现；
模式匹配（求子串位置的定位操作）的 BF算法
,KMP算法，以及求模式串 next录取数值的算法及修正算法
● 学习要点熟悉串的有关概念，
串和线性表的关系；掌握串的各种存储结构，比较它们各自的优缺点；熟悉串的各种基本操作，并能利用这些基本操作实现串的其它操作；掌握模式匹配的 BF算法,KMP算法以及求模式串的 next函数值及 nextval函数值 的方法及技巧。
