当前位置：文档之家 › 第四章 串

第四章 串

  • 格式：pdf
  • 大小：320.62 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

严蔚敏数据结构-第四章 串

严蔚敏数据结构-第四章 串
S1 4 a b c d S2 2 e f T 6 a b c d e f
15
(2)S1串长 最大串长 串长<最大串长 串长 最大串长; S1,S2串长和 最大串长 串长和>最大串长 串长和 最大串长;
S1 6 a b c d e f S2 6 g h i j k l T 8 a b c d e f g h
3
串的抽象数据类型的定义： 串的抽象数据类型的定义： ADT String{ 数据对象： 数据对象：D={ai|ai∈CharacterSet, i=1,2,...,n, n>=0} 数据关系： 数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=2,...,n} 基本操作： 基本操作： StrAssign(&T, chars)
11
作业： 作业： 1.用5种串的基本操作（StrAssign、StrCompare、StrLen Concat、SubString）来逻辑实现StrInsert(&S, pos, T)操作 、 操作. ）
Status StrInsert(String S, int pos , String T) { if ……….. return error; , , ); ); ); );
chars是字符串常量。生成一个其值等于chars的串 。 是字符串常量。生成一个其值等于 的串T。 是字符串常量 的串
StrCopy(&T, S)
存在则由串S复制得串 串S存在则由串 复制得串 存在则由串 复制得串T
StrEmpty(S)
存在则若S为空串 串S存在则若 为空串 返回真否则返回假 存在则若 为空串,返回真否则返回假
Sub返回串 的第pos个字符起长度为 返回串S的第 个字符起长度为len的子串 用Sub返回串S的第pos个字符起长度为len的子串

串的定义及其基本运算

串的定义及其基本运算

4.2串的定长顺序存储及基本运算
4.2.1存储结构的实现
#define MAXSIZE 256 第一种： typedef struct {char data[MAXSIZE]; int curlen; }SeqString;
0 s.data a 第二种： b c d e f g h i 1 2 3 4 5 6 7 8
j=1 j=3 j=2 j=4
i=2 i=4 i=3 i=5
j 模式串 next[j]
i=5
1 2
0 1
3
1
4
1
5
2
6
2
7
3
8
2
9
3
a b c a a b a b c
s： a a b c b a b c a a b c a a b a b c t： abcaababc
j=1 i=6 i=7i=8 i=10 i=12 i=9 i=11 i=10 i=12
MAXSIZE
4.2.2运算实现（采用第二种表示串长的方式） int StrLength(char s[]) 1. 求串的长度 StrLength(s)； {int len=0;
while(s[len]!=‘\0’)len++; return len; }
2.串赋值 void StrAssign(s1,s2) StrAssign(s1,s2); char s1[ ], s2[ ] ;
j=3 j=5 j=7 j=9 j=4 j=6 j=8 j=10
（3）KMP算法实现 循环条件？ 什么时候回溯？ 回溯时i、j如何计算？ 如何判断匹配是否成功？ 匹配成功时，返回的起始位置如何计算？
见P61的算法4-5

数据结构——第4章 串(C#)

数据结构——第4章 串(C#)
将当前链串的所有结点?nstr将q结点插入到尾部将q结点插入到尾部将链串t的所有结点?nstr将q结点插入到尾部尾结点的next置为null返回新建的链串5求子串substrij返回当前串中从第i个字符开始的连续j个字符组成的子串ຫໍສະໝຸດ 第4章 串4.1 串的基本概念
4.1.1 什么是串 串（或字符串）是由零个或多个字符组成的有限序列。 记作str="a1a2…an"（n≥0），其中str是串名，用双引号括 起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一 个任意字符（字母、数字或其他字符），它称为串的元素， 是构成串的基本单位，串中所包含的字符个数n称为串的 长度，当n=0时，称为空串。
4.2 串的存储结构
4.2.1 串的顺序存储结构－顺序串
和顺序表一样，用一个data数组（大小为MaxSize）和 一个整型变量length来表示一个顺序串，length表示data数 组中实际字符的个数。 定义顺序串类SqStringClass如下：
class SqStringClass { const int MaxSize=100; public char[] data; //存放串中字符 public int length; //存放串长 public SqStringClass() //构造函数,用于顺序串的初始化 { data=new char[MaxSize]; length=0; } //顺序串的基本运算 }
（9）串输出DispStr() 将当前串s的所有字符构成一个字符串并输出。对应的算 法如下：
public string DispStr() { int i; string mystr=""; if (length==0) mystr = "空串"; else { for (i=0;i<length;i++) mystr+=data[i].ToString(); } return mystr; }

数据结构第4章 串

数据结构第4章 串
ring s, SString t)
/*若串s和t相等则返回0；若s>t则返回正数；若s<t则返 回负数*/
{ int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]);
初 始 条 件 : 串 S 存 在 ,1≤pos≤StrLength(S) 且 1≤len≤StrLength(S)-pos+1
操作结果:用Sub返回串S的第pos个字符起长度为len的子串
返回主目录
（11）StrIndex(S,T,pos)
初始条件: 串S和T存在,T是非空串, 1≤pos≤StrLength(S)
return(s.len); }
返回主目录
（7）清空函数
StrClear(SString *s) /*将串s置为空串*/ {
s->len=0; }
返回主目录
（8）连接函数
(1) 连接后串长≤MAXLEN，则直接将B加在A的 后面。 (2) 连接后串长>MAXLEN且LA<MAXLEN，则B 会有部分字符被舍弃。 (3) 连接后串长>MAXLEN且LA=MAXLEN，则B 的全部字符被舍弃（不需连接）。
for (i=s->len + t.len-1;i>=t.len + pos;i--)
s->ch[i]=s->ch[i-t.len];
for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i];
s->len=s->len+t.len;

数据结构-第4章 串

数据结构-第4章 串
真子串是指不包含自身的所有子串。
4.1 串的类型定义
子串的序号：将子串在主串中首次出现时的该 子串的首字符对应在主串中的序号，称为子串 在主串中的序号（或位置）。 【例】 A=“abcdefbbcd”，B=“bcd”，B在A中的 序号为2。 特别地，空串是任意串的子串，任意串是其自 身的子串。
4.1.2 串的抽象数据类型定义
//查找ab子串
if (p->data==‘ a’ && p->next->data==‘b’)
{ p->data=‘x’; p->next->data=‘z’;
q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data=‘y’;
q->next=p->next; p->next=q;
s: a a a a b c d
t: a ab bac acb bc c ✓ 匹配成功 算法的思路是从s的每一个字符开始依次与t的 字符进行匹配。
4.2.1 Brute-Force算法
int BFIndex(SqString s,SqString t)
{ int i=0, j=0,k;
while (i<s.length && j<t.length)
4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法
本章要求
理解： 1、串的基本概念、类型定义 2、串的存储表示和实现 3、串的KMP算法
掌握： 4、串的简单模式匹配算法(BF)
第4章 串的基本概念
串（或字符串）：是由零个或多个字符组成 的有限序列。
串的逻辑表示： S=“a1a2…ai…an”，其中S为 串名，ai (1≤i≤n)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。

《数据结构与算法》第四章-学习指导材料

《数据结构与算法》第四章-学习指导材料

《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。

4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。

一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。

２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。

包含子串的串相应地称为主串。

子串的位置：子串的第一个字符在主串中的序号称为子串的位置。

串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。

4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。

4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。

如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。

如图4.1所示。

s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。

数据结构第四章串习题及答案

习题四串一、单项选择题‎1．下面关于串‎的的叙述中‎，哪一个是不‎正确的？（）A．串是字符的‎有限序列 B．空串是由空‎格构成的串‎C．模式匹配是‎串的一种重‎要运算 D．串既可以采‎用顺序存储‎，也可以采用‎链式存储2．串是一种特‎殊的线性表‎，其特殊性体‎现在（）。

A．可以顺序存‎储 B．数据元素是‎一个字符C．可以链接存‎储 D．数据元素可‎以是多个字‎符3．串的长度是‎指（）A．串中所含不‎同字母的个‎数 B．串中所含字‎符的个数C．串中所含不‎同字符的个‎数 D．串中所含非‎空格字符的‎个数4．设有两个串‎p和q，其中q是p‎的子串，求q在p中‎首次出现的‎位置的算法‎称为（）A．求子串 B．联接 C．匹配 D．求串长5．若串S=“softw‎a re”,其子串的个‎数是（）。

A．8 B．37 C．36 D．9二、填空题1．含零个字符‎的串称为_‎_____‎串。

任何串中所‎含____‎__的个数‎称为该串的‎长度。

2．空格串是指‎__ __，其长度等于‎__ __。

3．当且仅当两‎个串的__‎____相‎等并且各个‎对应位置上‎的字符都_‎_____‎时，这两个串相‎等。

一个串中任‎意个连续字‎符组成的序‎列称为该串‎的____‎__串，该串称为它‎所有子串的‎_____‎_串。

4．INDEX‎（‘DATAS‎T RUCT‎U RE’，‘STR’）=_____‎___。

5．模式串P=‘abaab‎c ac’的next‎函数值序列‎为____‎____。

6．下列程序判‎断字符串s‎是否对称，对称则返回‎1，否则返回0‎；如 f("abba")返回1，f("abab")返回0；int f((1)__ _____‎_){int i=0,j=0;while‎(s[j])(2)___ _____‎;for(j--; i<j && s[i]==s[j]; i++,j--);retur‎n((3)___ ____)}7．下列算法实‎现求采用顺‎序结构存储‎的串s和串‎t的一个最‎长公共子串‎。

第四章 串答案

第四章答案4.1 简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

答：●空串是指不包含任何字符的串，它的长度为零。

空白串是指包含一个或多个空格的串，空格也是字符。

●串常量是指在程序中只可引用但不可改变其值的串。

串变量是可以在运行中改变其值的。

●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。

●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。

●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。

4.2 假设有如下的串说明：char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;(1)在执行如下的每个语句后p的值是什么?p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');(2)在执行下列语句后，s3的值是什么?strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);(3)调用函数strcmp(s1,s2)的返回值是什么?(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?(5)调用函数stlen(strcat(s1,s2))的返回值是什么?解：(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。

第四章 串

主串S首次出现的位置；否则返回0
– 例如
• 主串S = • 子串T = CD • 则index(S,T)，返回子串T在S中，第一次出现的位置3
19
串的模式匹配
Brute-Force算法基本思想： • 从目标串s 的第一个字符起和模式串t的第一个字符进行比较 • 若相等，则继续逐个比较后续字符，否则从串s 的第二个字 符起再重新和串t进行比较。 • 依此类推，直至串t 中的每个字符依次和串s的一个连续的字 符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。
两式联立可得：“T0…Tk-1”= “Tj-k…Tj-1”
注意：j为当前已知的失配位置，我们的目标是计算新起点k。式中仅剩 一个未知数k，理论上已可解！
奇妙的结果：k仅与模式串T有关！
27
新起点k怎么求？
根据模式串T的规律：“T0…Tk-1”=“Tj-k …Tj-1” 由当前失配位置j(已知)，归纳计算新起点k的表达式。
j=next[j]的位置(即模式串继续向右移动)，再比较 si 和 tj 。
依次类推，直到下列两种情况之一： 1)j退回到某个j=next[j]时有 si = tj，则指针各增1，继续匹配； 2)j退回至j=0，此时令指针各增1，即下一次比较 si+1和 t0 。
30
串的模式匹配：KMP算法
• 模式串的next函数
6
串的基本概念
4.两个字符串相等的充分必要条件为两个字符串的长度相等，并 且对应位置上的字符相等。
例如：‘abcd’ ≠ ‘bacd’ ‘abcd’ = ‘abcd’
7
串的基本操作
1.给串变量赋值 ASSIGN(S1,S2)

数据结构第四章串


(2) 置换操作：用联接算法来实现。用在求子串序号（a,b，h）中得到的 ind 将a分成3部分：第一部分是b在a中的第一个位置前的子串substr （a,1,ind－1）;第二部分是b（以c来代替）；第三部分是b在a中的最后一个 位置后的子串substr（a,ind+m,n）。 即 a substr(a,I,ind-1)||c||substr(a,ind+m,n)
4. 2 串的基本运算
对于串的基本操作，许多高级语言均提供了相应的运算或标准 库函数来实现。下面仅介绍几种常用的串运算。 (1)联接(concatenation) 联接是串的最基本，最重要的运算。两个串的联接是将一个串 紧接着放在另一个串的末尾。联接用符号“||”表示。 例如：a＝”bei” b=“jing” a || b=“beijing” (2)求子串(substr) SUBSTR(a，m，n)功能: 从a 中截取子串，从第m个字符到第n个 字符的子串（m<n)。子串应是将串a中取出从标号m开始的连续n －m＋1个字符。 例：SUBSTR(“ABCDEFG”,2,3)＝”BC” 利用求子串及联接两种运算可以完成对串的插入、删除和修改。 例如： a＝“bejing” b=“iy” ，将b插入到a的第二个字符之后 得到新的串s，则 s=substr(a,1,2) || b || substr(a,3,6) =“beiyjing”
（5）置换(repleace) 置换运算repleace(a,b,c)表示在a中搜索b，若b是a的 子串，就以c代替b，若不是，则经置换后，a不变。 例如：a=“monday”, b=“mon”, c=“thurs” repleace(a,b,c)=“thursday” 置换运算是将串a中所有的子串b用c来代替。 在一部分程序设计语言中没有实现，仍可用前三种运 算来完成。 置换算法过程：实现置换运算repleace（a,b,c），同 样也是在a中搜索是否与b相同的子串，若有，以c来代 替，再继续向下搜，直到在a中找不到和b相同的子串 为止。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第四章 串
第一部分：知识点
一、串的概念
由零个或多个字符组成的有限序列，一般记作
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
6．字符串‘ababa a bab’ 的nextval 为（ ）
A．(0,1,0,1,0,4,1,0,1) B．(0,1,0,1,0,2,1,0,1) C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )
7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ ），nextval数组的值为 （ ）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
8. 设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。

n+(n-1)+…2=(n+2)*(n-1)/2
二、填空题
1．空格串是指__(1)__，其长度等于___(2)__。

2．组成串的数据元素只能是________。

3．一个字符串中________称为该串的子串 。

4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。

5．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。

6. 设T和P是两个给定的串，在T中寻找等于P的子串的过程称为__(1)__，又称P为__(2)__。

7.串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方式是__(2)__、__(3)__；两个串相等的充分必要条件是
__(4)__。