串
- 串的顺序实现
- 简单的模式匹配算法
- KMP算法
- KMP算法的进一步优化
串的顺序实现
初始化
#define MaxSize 50
typedef char ElemType;
//顺序存储表示
typedef struct{
Elem服务器托管网Type data[MaxSize];
int length;
}SString;
/**
* 初始化串
*/
void InitString(SString *string) {
for (int i = 0; i length; ++i) {//全部初始化为‘’
string->data[i] = '';
}
string->length = 0;//长度赋值为0
}
赋值操作
/**
* 赋值操作
*/
void StrAssign(SString *string, char *str) {
//循环赋值
for (int i = 0; i data[i] = str[i];
}
string->length = strlen(str);
}
复制操作
/**
* 复制操作:把串 str 复制到 string
*/
void StrCopy(SString *string, SString str) {
int i, j;
for (i = 0; i data[i] = str.data[i];
}
string->length = str.length;
}
判空操作
/**
* 判空操作
*/
bool StrIsEmpty(SString string) {
if (string.length == 0) {
return true;
} else {
return false;
}
}
比较操作
/**
* 比较操作:首先比较同位序的字母大小,其次比较字符串的长度大小
*/
int StrCompare(SString string, SString str) {
for (int i = 0; i
截取操作
/**
* 截取操作:用 sub 返回串 string 的第 pos 个字符起长度为 len 的子串
*/
bool SubString(SString *sub, SString string, int pos, int len) {
if (pos + len > string.length) {
return false;
}
for (int i = pos; i data[i - pos] = string.data[i];
}
sub->length = len;
return true;
}
连接操作
/**
* 连接操作:把两个串相连
*/
void StrConcat(SString *sub, SString string, SString str) {
int i;
for (i = 0; i data[i] = string.data[i];
}
for (int j = 0; j data[i] = str.data[j];
}
sub->length = string.length + str.length;
}
简单的模式匹配算法
所谓串的模式匹配算法,是一种专门定位子串在主串中位置的方法(方案、思想),整个定位的过程称为模式匹配。此外,在模式匹配的过程中,子串通常又被称为“模式串”。
串模式匹配的实现方法有很多种,本节先给大家讲一种最容易理解、最简单的方法,称为 BF 算法。
采用 BF 算法定位模式串在主串中的位置,就是简单粗暴的从主串的起始位置开始,不断地将模式串中的字符和主串中的字符进行对比。
具体来讲,假设对模式串 A(abcac
)和主串 B(ababcabacabab
)进行模式匹配,BF 算法的执行过程如下:
将模式串 A 与主串 B 的首字符对齐,逐个判断相对的字符是否相等
由于模式串 A 与主串 B 的第 3 个字符匹配失败,此时将模式串 A 后移一个字符的位置,采用同样的方法重新匹配
两个串依旧匹配失败,模式串 A 继续后移一个字符的位置
模式串 A 继续向后移动
模式串 A 与主串 B 共匹配了 6 次才成功,最终定位到模式串 A 位于主串 B 第 6 的位置处,整个模式匹配的过程就称为 BF 算法。
int Index(SString s,SString t){//s:主串,t:子串
int i = 0,j = 0;
while (it.length)
{
return i - t.length;
}else{
return 0;
}
}
KMP算法
学过 BF 算法的读者应该知道,该算法的实现思想很简单,就是 “傻瓜式” 地将模式串(假定为子串的串)与主串中的字符一一匹配。KMP 算法不一样,它可以略过一些原本就不可能成功的匹配过程,提高模式匹配的效率。
例如,对主串 A(“ABCABCE”)和模式串 B(“ABCE”)进行模式匹配,KMP 算法只需要匹配 2 次。
显示第一次匹配失败,从整个匹配过程可以获得的信息是:模式串中 “ABC” 和主串对应的字符相同,但模式串中的字符 ‘A’ 与 ‘B’ 和 ‘C’ 不同。这也就意味着,下次模式匹配时没必要再让串 B 中的 ‘A’ 与主串中的字符 ‘B’ 和 ‘C’ 一一匹配,它们绝不可能相等。
因此第二次模式匹配开始前,我们改变指针 j 的指向
模式串直接跳过主串中的第 2、3 个字符,从第 4 个字符处开始第二次模式匹配,最终匹配成功。KMP 算法的整个匹配过程只进行了 2 次,而如果用 BF 算法需要匹配 4 次。
和 BF 算法相比,KMP 算法只需要移动指针 j 的位置,可以略过一些原本就不可能成功的匹配过程,减少匹配的次数,提高模式匹配的效率。
对于初学者而言,KMP 算法最大的难点是:当模式匹配失败后,如何修改指针 j 的位置。
请大家先记住一句话:指针 j 的新位置只和模式串有关,与主串无关。接下来通过一个实例,给大家演示如何只通过模式串确定指针 j 的位置。
将模式串 B 改为 “ABCAE”,第一次匹配的过程如下图所示:
匹配失败时模式串中字符 ‘E’ 前的 ‘A’ 与模式串开头的 ‘A’ 相等,因此我们可以将指针 j 指向模式串中的第 2 个字符,下次直接从 i 和 j 的位置开始匹配,这就是 KMP 算法重定位指针 j 的方法。
也就是说,模式匹配失败后指针 j 的新位置可以通过匹配失败位置前的字符计算得出。进一步讲,只要给定一个模式串,我们就可以确定匹配失败后指针 j 的新位置。
当模式串和主串进行模式匹配时,模式串中的每个字符都可能导致匹配失败,而失败后指针 j 的新位置是可以计算出来的。模式串中有多少个字符,就可以计算出多少个指针 j 的新位置,它们是一一对应的关系。我们通常会各个字符对应的 j 的新位置存储到一个数组中,并给这个数组起名为 Next 数组,数组中的值统称为 next 值。
模式串中各个字符对应的 next 值的计算方式是,取该字符前面的字符串(不包含自己),其前缀字符串和后缀字符串相同字符的个数再 +1 就是该字符对应的 next 值。
前缀字符串指的是位于模式串起始位置的字符串,例如模式串 “ABCD”,则 “A”、“AB”、“ABC” 都属于前缀字符串;后缀字符串指的是位于串结尾处的字符串,还拿模式串 “ABCD” 来说,“D”、“CD”、“BCD” 为后缀字符串。
注意,模式串中第一个字符对应的值为 0,第二个字符对应的值是 1 ,这是固定不变的。因此模式串 “ABCAE” 中各个字符对应的 next 值如图
各个字符对应 next 值的计算过程是:
- 第三个字符 ‘C’:在前面的字符串 “AB” 中,前缀字符串和后缀字符串相等个数为 0,0 + 1 = 1,所以字符 ‘C’ 对应的 next 值为 1。
- 第四个字符 ‘A’:在前面的字符串 “ABC” 中,前缀字符串和后缀字符串相等个数为 0,0 + 1 = 1,所以字符 ‘A’ 对应的 next 值为 1。
- 第五个字符 ‘E’:在前面的字符串 “ABCA” 中,前缀字符串和后缀字符串相等个数为 1,1 + 1 = 2,所以字符 ‘E’ 对应的 next 值为 2。
当字符 ‘E’ 匹配失败时,指针 j 指向模式串数组中第 2 个字符,即 ‘B’
那么,如果编写程序计算出模式串对应的 NEXT 数组呢?
可以设计这样一个算法:刚开始时令 j 指向模式串中第 1 个字符(j=1),i 指向第 2 个字符(i=2)。接下来,对每个字符做同样的操作:
-
如果 i 和 j 指向的字符相等,则 i 后面第一个字符的
ne服务器托管网xt
值为 j+1,同时 i 和 j 做自加 1 操作,为求下一个字符的next
值做准备; -
如果 i 和 j 指向的字符不相等,则执行
j=next[j]
修改 j 的指向,然后以同样的方法对比 i 和 j 指向的字符,以此类推。当 j 的值为 0 时,将 i 后面第一个字符的 next 值置为 1。
例如,计算模式串 “aaacd” 对应的 NEXT 数组,实现过程为:
- 前两个字符对应的 next 值分别为 0 和 1(j=1, i=2);
- 由于 i 和 j 指向的字符相等,所以第三个字符 ‘a’ 的 next 值为 j +1 = 2,同时 i 和 j 各自加 1(此时 j=2,i=3)。
- 由于 i 和 j 指向的字符相等,所以第四个字符 ‘c’ 的 next 值为 j +1 = 3,同时 i 和 j 各自加 1(此时 j=3,i=4)。
- 此时 i 和 j 指向的字符不相等,执行 j = next[j] 修改 j 的指向
- 从上图可以看到,i 和 j 指向的字符又不相同,继续执行 j = next[j]
由于 j 和 i 指向的字符仍不相等,继续执行 j=next[j] 得到 j=0,字符 ‘d’ 对应的 next 值为 1。
实际上,当第一次比较 i 和 j 不相等时,意味着匹配失败位置前的最长前缀和后缀字符串不相同;执行 j=next[j] 后,i 和 j 仍不相等,意味着匹配失败位置前的次长前缀和后缀字符串也不相同,以此类推。当 j = 0 时,意味着匹配失败位置前没有相等的前缀和后缀字符串。
这里给出上述思想实现 NEXT 数组的 C 语言代码:
void GetNext(SString string,int* next){//string是字串
int i = 1,j = 0;
//next的第一个元素固定为0
next[i] = 0;
while (i
假设主串 A 为 “ababcabcacbab”,模式串 B 为 “abcac”,KMP 算法进行模式匹配的过程为:
- 第一次匹配如图所示,匹配结果失败,指针 j 移动至 next[j] 的位置;
- 第二次匹配如图所示,匹配结果失败,执行 j=next[j] 操作
- 第三次匹配成功
使用 KMP 算法只需匹配 3 次,而同样的问题使用 BF 算法则需匹配 6 次才能完成。
KMP 算法:
int KMP(SString s,SString t,int* next){
int i = 1,j = 1;
while (it.length)
{
return i - t.length;
}else{
return 0;
}
}
KMP算法的进一步优化
只需要更改next
即可
void GetNextVal(SString string,int* next){//string是字串
int i = 1,j = 0;
//next的第一个元素固定为0
next[i] = 0;
while (i
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 前端开发如何更好的避免样式冲突?级联层(CSS@layer)
作者:vivo 互联网前端团队 – Zhang Jiqi 本文主要讲述了CSS中的级联层(CSS@layer),讨论了级联以及级联层的创建、嵌套、排序和浏览器支持情况。级联层可以用于避免样式冲突,提高代码可读性和可维护性。 一、什么是级联层(Cascade L…