大家好,欢迎来到IT知识分享网。
定义
内容受限的线性表
串(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算法
算法思想:利用已经部分匹配的结果而加快模式串的滑动速度,而主串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];
}
}
}
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/92733.html