4.1 串及其运算是由零个或多个字符组成的有限序列，一般记为
s=“a1a2…a n”(n?0)
其中,s是串名，用单引号（也可以是用双引号括起来的）
括起来的字符序列是串的值。 ai可以是字母、数字或其他字符；串中字符的个数 n成为串的长度。
第四章 串子串,串中任意个 连续 的字符组成的子序列。
主串,包含子串的串相应地称为主串。
位置,字符在序列中的序号。子串在主串中的位置则以子串的 第一个 字符在主串中的位置来表示。
相等,两个串的长度相等，并且对应位置的字符都相等。
注意区分 空串 与 空格串 的区别。
串的逻辑结构和线性表的区别,
1,串的数据对象约束为字符集。
2,线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。
对于串可以定义以下运算：
1,置串为一个空串；
2,判断一个串是否为空串
3.
4.
5,在一个串中,求从串的第 i个字符开始连续 j个字符所
6,如果串 S2是 S1的子串,则可求串 S2在串 S1中第一次出现的位置 。
1,定长顺序表示
#define MAXNUM 1000 /* 串允许的最大字符个数 */
struct SeqString /* 顺序串的类型 */
{
char c[MAXNUM];
int n;
}SeqString,*PSeqString;
4.2串的存储表示
PSeqString subStr_seq(PSeqString s,int i,int j)
/* 求从 s所指的顺序串中第 i(i>0)个字符开始连续 j个字符所构成的子串 */
{ PSeqString s1;
int k,m;
s1 = createNullStr_seq( );
if (s1==NULL) return NULL;
if ( i>0 && i<=s->n && j>0 )
{
if ( s->n < i+j-1 ) j = s->n -i+1;
for (k=0;k<j;k++)
s1->c[k]=s->c[i+k-1];
s1->c[j]='\0';
s1->n =j; }
else s1->c[0]='\0';
return(s1);
}
算法 4.1 求顺序表示的串的子串
PSeqString createNullStr_seq( void )
{
PSeqString pstr;
pstr=(PSeqString)malloc(sizeof(struct SeqString));
if (pstr==NULL)
printf("Out of space!!\n");
else
pstr->n = 0;
return pstr;
}
算法 4.2 创建空顺序串
typedef struct
{ char *ch;
int length;
}HString;
void StrAssign(HString *str,char *chars);
void StrCopy(HString *dest,HString src);
void StrCopyN(HString *dest,HString src,int n);
BOOL IsStrEmpty(HString str);
int StrCompare(HString str1,HString str2);
int StrLength(HString str);
void ClearString(HString *str);
Status StrCat(HString *dest,HString str1,HString str2);
……
2,变长顺序表示
void StrAssign(HString *str,char *chars) {
char *p = chars;
int length,i;
if(str->ch) /* 释放已有空间 */
{ free(str->ch);
str->ch = NULL;
str->length = 0; }
while(*p!=‘#’) p++ ; /* 求串长 */
length = p - chars - 1;
if(length == 0) str->length = 0;
else{ /* 重新申请空间 */
str->length = length;
str->ch = (char *)malloc(sizeof(char)*length);
assert(str->ch);
for(i=0; i<length; i++) str->ch[i] = chars[i];
}
} /* End of StrAssign() */
void StrCopy(HString *dest,HString src)
{ char *p;
int i;
if(dest->ch)
{
free(dest->ch);
dest->ch = NULL;
}
p = (char *)malloc(sizeof(char) * src.length);
assert(p);
dest->ch = p;
dest->length = src.length;
for(i=0; i<src.length; i++) p[i] = src.ch[i];
}
for(i=0; i<src.length; i++) p[i] = src.ch[i];
dest->ch = p;
dest->length = src.length;
提取子串的算法示例
pos+len -1 pos+len -1
curLen-1? curLen
i n f i n i t y i n f i n i t y
pos = 2,len = 3 pos = 5,len = 4
f i n i t y
超出
Status SubString(HString *sub,HString str,int pos,int len)
{/* 0 <= pos < str.length and 0 <= len <= str.length-pos+1
用 sub返回串 str的第 pos个字符起长度为 len的子串 */
int i;
if(pos < 0 || pos >= str.length || len < 0 || len > str.length-pos+1)
return ERROR;
if(sub->ch){ free(sub->ch);
sub->ch = NULL; }
if(!len){ sub->ch = NULL;
sub->length = 0; }
else{ sub->ch = (char *)malloc(sizeof(char) * len);
assert(sub->ch);
for(i=0; i<len; i++) str->ch[i] = str[pos+i];
sub->length = len; }
return OK;
} /* End of SubString() */
#define ChunkSize 80
typedef struct _StrNode
{ char c;
struct _StrNode *link;
}StrNode;
typedef struct
{ StrNode *head;
}LinkString,*PLinkString,*PStrNode;
4,串的块链存储表示
(a) 单链表表示
(b) 循环表表示四、模式匹配与 KMP算法
模式匹配
在一个源串中搜索模式串的出现位置源串,"This is a demo string!"
模式串,"is a"
四、模式匹配与 KMP算法
朴素模式匹配算法
This is a demo string!is ais ais ais ais ais a 模式串,is a源串：
四、模式匹配与 KMP算法
KMP算法
问题的提出 ——一个极端的例子
aaaaaaaaaab
aaaabaaaabaaaabaaaabaaaabaaaabaaaab
模式串,aaaab源串：
四、模式匹配与 KMP算法
KMP算法
算法思想 ——nextval向量模式串,aaaabaaaaaaaabaaaab
下标,01234
nextval[4]=3
源串：
四、模式匹配与 KMP算法
KMP算法
算法思想 ——nextval向量模式串,aaaaaaaaaaaaaaaaaaa
下标,01234
nextval[4]=-1
源串：
四、模式匹配与 KMP算法
KMP算法
nextval向量的定义
对模式串 T[0…n-1]，
定义向量 nextval[0…n-1]如下：
nextval[i]表示：
当 T[i]匹配失败时，下一次必要的匹配比较是用 T[nextval[i]]与源串的当前字符进行比较；
若模式串已不可能与源串的当前位置形成匹配，
则记 nextval[i]为一个特殊值，如 -1。
四、模式匹配与 KMP算法
KMP算法
nextval向量举例
i 0 1 2 3 4 5 6 7 8
T a b a b a b c b a
nextval -1 0 -1 0 -1 0 4 0 -1
四、模式匹配与 KMP算法
KMP算法
在 nextval向量指导下进行模式匹配
在源串和模式串上分别设立扫描指针 i和 j，从串首开始；
对源串和模式串的当前字符进行比较，直到源串或模式串扫描完毕：
若相等，则两个扫描指针同步前进；
否则，模式串扫描指针前移到 nextval向量指示的位置，若 nextval[i]为预定特殊值，则源串扫描指针前进，模式串扫描指针回到串首；
若模式串扫描完毕，则匹配成功，否则匹配失败。
CODING
四、模式匹配与 KMP算法
KMP算法
nextval向量的计算
nextval向量的性质
最大相同首真子串与尾真子串
↓
源 … sj-i … sj-i+k-1 sj-i+k … sj-k … sj-1 sj …
模
t0 … tk-1 tk … ti-k … ti-1 ti …
t0 … tk-1 tk …
最大相同首真子串与尾真子串
1,sj-i~sj-1=t0~ti-1(ti之前已经匹配成功 )
2,sj≠ti（ ti匹配失败）
3,t0~tk-1=ti-k~ti-1（根据模式串可以确定的可匹配部分）
4,不存在更大的满足条件 3和 5的 k值（以保证匹配的必要性）
5,ti≠tk（若 ti=tk，则不须比较即可推知,sj≠tk）
↓
源 … sj-i … sj-i+k-1 sj-i+k … sj-k … sj-1 sj …
模
t0 … tk-1 tk … ti-k … ti-1 ti …
t0 … tk-1 tk …
前提条件
k为最大相同首真子串和尾真子串的长度
k即 nextval[i]
四、模式匹配与 KMP算法
KMP算法
最大相同首真子串与尾真子串的长度的计算
将 T[0…i-1]的最大相同首真子串与尾真子串的长度，记为 Ki
设已知 Ki-1，求 Ki：
1,令 k从 Ki-1开始；
2,若 k=-1（特殊值），则 Ki=0；
3,若 t[k]=t[i-1]，则 Ki=k+1；
4,否则，将 k前推至 nextval[k]，重复 2；
模
t0 … tk-1 … ti-1-k … ti-2 ti-1 ti
t0 … tk-1 tk
四、模式匹配与 KMP算法
KMP算法
nextval向量的计算
计算 nextval[i]：
先计算 T[0…i-1]的最大相同首真子串与尾真子串的长度 Ki；
如果 T[i]≠T[Ki]，则 nextval[i]=Ki，
否则 nextval[i]=nextval[Ki]
i 0 1 2 3 4 5 6 7 8
T a b a b a b c b a
K -1 0 0 1 2 3 4 0 0
nextval -1 0 -1 0 -1 0 4 0 -1
CODING
s=“a1a2…a n”(n?0)
其中,s是串名，用单引号（也可以是用双引号括起来的）
括起来的字符序列是串的值。 ai可以是字母、数字或其他字符；串中字符的个数 n成为串的长度。
第四章 串子串,串中任意个 连续 的字符组成的子序列。
主串,包含子串的串相应地称为主串。
位置,字符在序列中的序号。子串在主串中的位置则以子串的 第一个 字符在主串中的位置来表示。
相等,两个串的长度相等，并且对应位置的字符都相等。
注意区分 空串 与 空格串 的区别。
串的逻辑结构和线性表的区别,
1,串的数据对象约束为字符集。
2,线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。
对于串可以定义以下运算：
1,置串为一个空串；
2,判断一个串是否为空串
3.
4.
5,在一个串中,求从串的第 i个字符开始连续 j个字符所
6,如果串 S2是 S1的子串,则可求串 S2在串 S1中第一次出现的位置 。
1,定长顺序表示
#define MAXNUM 1000 /* 串允许的最大字符个数 */
struct SeqString /* 顺序串的类型 */
{
char c[MAXNUM];
int n;
}SeqString,*PSeqString;
4.2串的存储表示
PSeqString subStr_seq(PSeqString s,int i,int j)
/* 求从 s所指的顺序串中第 i(i>0)个字符开始连续 j个字符所构成的子串 */
{ PSeqString s1;
int k,m;
s1 = createNullStr_seq( );
if (s1==NULL) return NULL;
if ( i>0 && i<=s->n && j>0 )
{
if ( s->n < i+j-1 ) j = s->n -i+1;
for (k=0;k<j;k++)
s1->c[k]=s->c[i+k-1];
s1->c[j]='\0';
s1->n =j; }
else s1->c[0]='\0';
return(s1);
}
算法 4.1 求顺序表示的串的子串
PSeqString createNullStr_seq( void )
{
PSeqString pstr;
pstr=(PSeqString)malloc(sizeof(struct SeqString));
if (pstr==NULL)
printf("Out of space!!\n");
else
pstr->n = 0;
return pstr;
}
算法 4.2 创建空顺序串
typedef struct
{ char *ch;
int length;
}HString;
void StrAssign(HString *str,char *chars);
void StrCopy(HString *dest,HString src);
void StrCopyN(HString *dest,HString src,int n);
BOOL IsStrEmpty(HString str);
int StrCompare(HString str1,HString str2);
int StrLength(HString str);
void ClearString(HString *str);
Status StrCat(HString *dest,HString str1,HString str2);
……
2,变长顺序表示
void StrAssign(HString *str,char *chars) {
char *p = chars;
int length,i;
if(str->ch) /* 释放已有空间 */
{ free(str->ch);
str->ch = NULL;
str->length = 0; }
while(*p!=‘#’) p++ ; /* 求串长 */
length = p - chars - 1;
if(length == 0) str->length = 0;
else{ /* 重新申请空间 */
str->length = length;
str->ch = (char *)malloc(sizeof(char)*length);
assert(str->ch);
for(i=0; i<length; i++) str->ch[i] = chars[i];
}
} /* End of StrAssign() */
void StrCopy(HString *dest,HString src)
{ char *p;
int i;
if(dest->ch)
{
free(dest->ch);
dest->ch = NULL;
}
p = (char *)malloc(sizeof(char) * src.length);
assert(p);
dest->ch = p;
dest->length = src.length;
for(i=0; i<src.length; i++) p[i] = src.ch[i];
}
for(i=0; i<src.length; i++) p[i] = src.ch[i];
dest->ch = p;
dest->length = src.length;
提取子串的算法示例
pos+len -1 pos+len -1
curLen-1? curLen
i n f i n i t y i n f i n i t y
pos = 2,len = 3 pos = 5,len = 4
f i n i t y
超出
Status SubString(HString *sub,HString str,int pos,int len)
{/* 0 <= pos < str.length and 0 <= len <= str.length-pos+1
用 sub返回串 str的第 pos个字符起长度为 len的子串 */
int i;
if(pos < 0 || pos >= str.length || len < 0 || len > str.length-pos+1)
return ERROR;
if(sub->ch){ free(sub->ch);
sub->ch = NULL; }
if(!len){ sub->ch = NULL;
sub->length = 0; }
else{ sub->ch = (char *)malloc(sizeof(char) * len);
assert(sub->ch);
for(i=0; i<len; i++) str->ch[i] = str[pos+i];
sub->length = len; }
return OK;
} /* End of SubString() */
#define ChunkSize 80
typedef struct _StrNode
{ char c;
struct _StrNode *link;
}StrNode;
typedef struct
{ StrNode *head;
}LinkString,*PLinkString,*PStrNode;
4,串的块链存储表示
(a) 单链表表示
(b) 循环表表示四、模式匹配与 KMP算法
模式匹配
在一个源串中搜索模式串的出现位置源串,"This is a demo string!"
模式串,"is a"
四、模式匹配与 KMP算法
朴素模式匹配算法
This is a demo string!is ais ais ais ais ais a 模式串,is a源串：
四、模式匹配与 KMP算法
KMP算法
问题的提出 ——一个极端的例子
aaaaaaaaaab
aaaabaaaabaaaabaaaabaaaabaaaabaaaab
模式串,aaaab源串：
四、模式匹配与 KMP算法
KMP算法
算法思想 ——nextval向量模式串,aaaabaaaaaaaabaaaab
下标,01234
nextval[4]=3
源串：
四、模式匹配与 KMP算法
KMP算法
算法思想 ——nextval向量模式串,aaaaaaaaaaaaaaaaaaa
下标,01234
nextval[4]=-1
源串：
四、模式匹配与 KMP算法
KMP算法
nextval向量的定义
对模式串 T[0…n-1]，
定义向量 nextval[0…n-1]如下：
nextval[i]表示：
当 T[i]匹配失败时，下一次必要的匹配比较是用 T[nextval[i]]与源串的当前字符进行比较；
若模式串已不可能与源串的当前位置形成匹配，
则记 nextval[i]为一个特殊值，如 -1。
四、模式匹配与 KMP算法
KMP算法
nextval向量举例
i 0 1 2 3 4 5 6 7 8
T a b a b a b c b a
nextval -1 0 -1 0 -1 0 4 0 -1
四、模式匹配与 KMP算法
KMP算法
在 nextval向量指导下进行模式匹配
在源串和模式串上分别设立扫描指针 i和 j，从串首开始；
对源串和模式串的当前字符进行比较，直到源串或模式串扫描完毕：
若相等，则两个扫描指针同步前进；
否则，模式串扫描指针前移到 nextval向量指示的位置，若 nextval[i]为预定特殊值，则源串扫描指针前进，模式串扫描指针回到串首；
若模式串扫描完毕，则匹配成功，否则匹配失败。
CODING
四、模式匹配与 KMP算法
KMP算法
nextval向量的计算
nextval向量的性质
最大相同首真子串与尾真子串
↓
源 … sj-i … sj-i+k-1 sj-i+k … sj-k … sj-1 sj …
模
t0 … tk-1 tk … ti-k … ti-1 ti …
t0 … tk-1 tk …
最大相同首真子串与尾真子串
1,sj-i~sj-1=t0~ti-1(ti之前已经匹配成功 )
2,sj≠ti（ ti匹配失败）
3,t0~tk-1=ti-k~ti-1（根据模式串可以确定的可匹配部分）
4,不存在更大的满足条件 3和 5的 k值（以保证匹配的必要性）
5,ti≠tk（若 ti=tk，则不须比较即可推知,sj≠tk）
↓
源 … sj-i … sj-i+k-1 sj-i+k … sj-k … sj-1 sj …
模
t0 … tk-1 tk … ti-k … ti-1 ti …
t0 … tk-1 tk …
前提条件
k为最大相同首真子串和尾真子串的长度
k即 nextval[i]
四、模式匹配与 KMP算法
KMP算法
最大相同首真子串与尾真子串的长度的计算
将 T[0…i-1]的最大相同首真子串与尾真子串的长度，记为 Ki
设已知 Ki-1，求 Ki：
1,令 k从 Ki-1开始；
2,若 k=-1（特殊值），则 Ki=0；
3,若 t[k]=t[i-1]，则 Ki=k+1；
4,否则，将 k前推至 nextval[k]，重复 2；
模
t0 … tk-1 … ti-1-k … ti-2 ti-1 ti
t0 … tk-1 tk
四、模式匹配与 KMP算法
KMP算法
nextval向量的计算
计算 nextval[i]：
先计算 T[0…i-1]的最大相同首真子串与尾真子串的长度 Ki；
如果 T[i]≠T[Ki]，则 nextval[i]=Ki，
否则 nextval[i]=nextval[Ki]
i 0 1 2 3 4 5 6 7 8
T a b a b a b c b a
K -1 0 0 1 2 3 4 0 0
nextval -1 0 -1 0 -1 0 4 0 -1
CODING
