定义

内容受限的线性表

串(string):零个或者多个任意字符组成的有限序列

字串：串中任意个连续字符组成的字序列

主串：包含子串的串相应地 字符位置：字符在序列中序号为该字符在串中的位置

字串位置：字串第一个字符在主串中的位置 空格串：由一个或多个空格组成的串，与空串不同

串相等：当且仅当两个串的长度相等并且各个对应位置上字符相同时，这两个串才是相等的

数学表示

S=“a1a2……an”(n>=0)

注: - S为串名 - a1a2……an为串值 - n为串长

抽象类型定义

ADT String {

数据对象: D={ ai | ai∈ CharacterSet,记为 V,i=1 ,2 ,…, n,n≥ 0 }

结构关系: R={< ai,ai + 1 >| ai,ai + 1 ∈ V,i=1 ,…, n-1 ; n-1 ≥ 0 }

基本操作:

StrAssign(&T,chars)//串赋值

操作前提: chars 是字符串常量。

操作结果:生成一个值等于 chars 的串 T。

StrInsert( S,pos,T)//字串插入

操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)+ 1 。

操作结果:在串 S 的第 pos 个字符之前插入串 T。

StrDelete( S,pos,len)

操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)+ 1 。

操作结果:从串 S 中删除第 pos 个字符起长度为 len 的子串。

StrCopy( S,T)

操作前提:串 S 存在。

操作结果:由串 T 复制得串 S。

StrEmpty( S)

操作前提:串 S 存在。

操作结果:若串 S 为空串,则返回 TRUE,否则返回 FALSE。

StrCompare(S,T) //串比较

操作前提:串 S 和 T 存在。

操作结果:若 S>T,则返回值>0 ;如 S=T,则返回值=0 ;若 S<T,则返回值<0 。

StrLength(S)

操作前提:串 S 存在。

操作结果:返回串 S 的长度,即串 S 中的字符个数。

StrClear( S)

操作前提:串 S 存在。

操作结果:将 S 清为空串。

ConCat(&T，S1,S2)

操作前提:串 S1 、S2 和 T 存在。

操作结果:将串 S1 和 S2 的值连接在串 T 的后面。

SubString( Sub,S,pos)

操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)且 1 ≤ len≤ StrLength( S)- pos+1

操作结果:用 Sub 返回串 S 的第 pos 个字符起的子串。

StrIndex( S,pos,T)

操作前提:串 S 和 T 存在,T 是非空串,1 ≤ pos≤ StrLength( S)。

操作结果:若串 S 中存在和串 T 相同的子串,则返回它在串 S 中第 pos 个字符 之后第一次出现的位置;否则返回 0 。

StrReplace( S,T,V)

操作前提:串 S、 T 和 V 存在且 T 是非空串。

操作结果:用 V 替换串 S 中出现的所有与 T 相等的不重叠的子串。

StrDestroy( S)

操作前提:串 S 存在。

操作结果:销毁串 S。

}ADT string

顺序存储结构

#define MAXSIZE 255

typedef struct{

char ch[MAXSIZE+1];//存储串的一维数组

int Length;//串的当前长度

}SString

链式存储结构

#define CHUNKSIZE 80 //块的大小可由用户定义

typedef struct Chunk{

char ch[CHUNKSIZE];

struct Chunk *next;

}Chunk;

typedef struct{

Chunk *head, *tail;//串的头指针和尾指针

int curlen;//串的当前长度

}LString;//字符串的块链结构

模式匹配算法算法的目的： 确定主串中所含字串第一次出现的位置算法的应用：搜索引擎、拼写错误、语言翻译、数据压缩算法种类：BF算法KMP算法(速度快)1.BF算法

Brute-Force简称BF算法，亦称为简单匹配算法，采用穷举法的思路

算法思路：从S的每一个字符开始依次与T的字符进行匹配

实现：

Index(S,T,pos) - 将主串的第pos个字符和模式串(字串)的第一个字符比较

- 若相等，继续逐个比较后续字符 - 若不等，从主串的下一个字符起，重新与模式串的第一个字符比较 - 直到主串的一个连续字串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功 - 否则，匹配失败，返回值为0

int Index_BF(SString S,SString T,int pos ){

int i = pos;

int j = 1;//字符的序号从1开始

while(i<=S.length && j<=T.length){

if(s.ch[i]==t.ch[j]){

++i;

++j;//主串和字串依次匹配下一个字符

}

else{

i = i - j + 2;//主串则向前移动一个字符

j = 1;//字串返回到第一个字符

}

}

//这里j>T.lngth是因为字串T的最后一个字符和主串的字符还是一样，那么进入while循环后又++j，所以只要j.length大于T的字符长度则说明全部字符都匹配成功

if(j>T.length) return i-T.length;//返回匹配的第一个字符的下标

else return 0;//模式匹配不成功

}

2.KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出，简称KMP算法

该算法较BF算法有较大的改进，从而使算法效率有了某种程度的提高

算法思想：利用已经部分匹配的结果而加快模式串的滑动速度，而主串S的指针i不必回溯，可提速到O(n+m)

主串和模式串不断比较，如果在比较失败，主串的i不用回溯到比较字符中第一个字符的第二个字符，而只用模式串j进行回溯，与主串再次进行下一轮比较，在这个过程中，我们用next[j]存储需要回溯到重新比较的值

image.png

代码实现

int Index KMP (SString S,SString T, int pos) {

i= pos,j =1;

while(i<S.length && j<T.length) {

if (j==0 S.chi]==T.ch[j]) {

i++;j++;

}

else{

j=next[j];//i不变，j后退

}

}

if (j>T.length) return i-T.length; //匹配成功

else return 0;//返回不匹配的标志

void get_next(SString T, int &next[]){

int i= 1;

next[1] = 0;

int j = 0;

while( i<T.length){

if(j==0||T.ch[i] == T.ch[j]){

++i; ++j;

next[i] = j;

}

else{

j = next[j];

}

}

}