- 1:串长、空串、空格串、子串、主串
- 1.1:串是一种特殊的线性表,数据元素之间呈线性关系
- 1.2:串的基本操作
- 1.3:串的模式匹配
串:串是由零个或多个字符串组成的有限序列,又名叫字符串 。一般记为
S = 'a_1a_2...a_n' (n>=0)
其中,S是串名,单括号内的字符序列是串的值。
串长、空串、空格串、子串、主串
串长:串中字符的个数n。例:'abc' , n=3
空串:n=0时的串称为空串。
空格串:由一个或多个空格组成的串。例: ' ' (4个空格),n=4
子串:串中任意个连续的字符组成的子序列。例如:A='hello world',B='hello',C='word',B和C都是A的子串
主串:包含子串的串。上面例子中A就是主串
串的位置:某个字符在串中的序号称为该字符在串中的位置。上例中B在A中的位置是1,C在A中的位置是7.
串是一种特殊的线性表,数据元素之间呈线性关系
串的数据对象限定为字符集
串的基本操作大多以“子串”作为操作对象
串的基本操作
- StrCopy (&T,S),复制操作,由串S复制得到串T。
-
Index (S,T),定位操作,找到串T在主串S中的位置。
-
StrLength (S),求串长,返回串S的元素个数。
-
StrCompare (S,T);比较操作。若S>T,则返回值>0,若S=T,则返回值=0,若S<T,则返回值<0。
【注】每个字符在计算机中对应一个二进制数,比较字符的大小就是比较二进制数的大小
串的模式匹配
子串的定位操作通常称为串的模式匹配,它求的是子串(常称为模式串)在主串中的位置。
简单的模式匹配算法(朴素模式匹配)
将主串S中与需要定位的子串相同长度的字符拎出来,挨个与子串匹配。若子串与模式串某个字符不匹配时,立即放弃该子串,转而检索下一子串。
例:主串:'abacababc' 模式串:'abc'
主串中与模式串长度相同的子串有'aba','bac','aca','cab','aba','bab','abc'。(也可以直接比较,不拎出来,看个人理解)依次与模式串比较,最后得到模式串在主串中的位置是7。
//暴力模式匹配
int Index(SString S,SString T){ //主串S,模式串T
int i=1,j=1;
while(i<=S.length && j<=T.length){
if(S.ch[i]==T.ch[j]){ //字符相同就比较下一个字符
++i;
++j;
}
else{
i=i-j+2;
j=1; //指针后退重新开始匹配
}
}
if(j>T.length) return i-T.length;
else return 0;
}
若模式串长度为m,主串长度为n,则直到匹配成功/匹配失败最多需要(n-m+1)*m次比较
最坏时间复杂度: 0(nm)
最坏情况:每个子串的前m-1个字符都和模式串匹配,只有第m个字符不匹配,比较好的情况:每个子串的第1个字符就与模式串不匹配
朴素模式匹配算法的缺点:当某些子串与模式串能部分匹配时,主串的扫描指针i经常回溯,导致时间开销增加。最坏时间复杂度0(nm)
KMP算法
当子串和模式串不匹配时,主串指针i不回溯,模式串指针j=next[j]。next[j]的含义是:在子串的第j个字符与主串失配时,则跳到子串的next[j]位置重新与主串当前位置进行比较。
next数组手算方法:当第j个字符匹配失败,由前1~j-1个字符组成的串记为S,则:
next[j]=S的最长相等前后缀长度+1,特别地,next[1]=0;值得注意的是,有些地方next[1]=-1,这也是没问题的,只要计算出的数组所有数都减一就可,其实就是最长相等的前后缀长度。
例:主串:'abacababacaabacb' 模式串:'abacb'
编号 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
模式串 | a | b | a | c | b |
next[j] | 0 | 1 | 1 | 2 | 1 |
//获取next数组
void get_next(SString T,int next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if(j==0 || T.ch[i]==T.ch[j]){
++i;++j;
next[i]=j;
}
else
j=next[j];
}
}
//KMP算法
int Index_KMP(SString S,SString T,int next[]){
int i=1,j=1;
while(i<=S.length && j<=T.length){
if(j==0 || S.ch[i]==T.ch[j]){
++i;
++j; //继续比较后继字符
}
else
j=next[j]; //模式串向右移动
}
if(j>T.length)
return i-T.length; //匹配成功
else
return 0;
}
算法平均时间复杂度: 0(n+m)
KMP算法进一步优化
nextval数组的求法:先算出next数组,先令nextval[1]=0,比较模式串中字符与其对应next[j]位置的字符是否相同,若相同,则将next[j]的值设为一致,否则不做改变。
上个例子中的nextval[j]的结果为:
编号 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
模式串 | a | b | a | c | b |
next[j] | 0 | 1 | 1 | 2 | 1 |
nextval[j] | 0 | 1 | 0 | 2 | 1 |
当子串和模式串不匹配时j=nextvalj];
//获取nextval数组
void get_nextval(SString T,int nextval[]){
int i=1,j=0;
nextval[1]=0;
while(i<T.length){
if(j==0 || T.ch[i]==T.ch[j]){
++i;++j;
if(T.ch[i]!=T.ch[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}