D3-串

储存串的结构有三种：

1.定长顺序存储

#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN + 1];//0号单元储存串的长度

若串长大于事先定义的长度，称截断，只保留MAXSIZE的长度

2.堆分配存储表示

typedef struct {char* ch;int length;
}HString;

3.串的块链存储表示

typedef struct _chunk {char ch[MAXSIZE];struct _chunk* next;
}CHUNK;typedef struct {CHUNK* head;CHUNK* tail;int length;
}LString;
//块链，类似线性表

串的模式匹配算法

1.简单算法

int Index(SString S, SString T, int pos) {//返回子串T在S中第pos个字符之后的位置，若没有则返回0int i = 0, j = 0;//i为主串的指针，j是子串的指针while (i < S[0] && j < T[0]) {if (S[i] == T[j]) {++i;++j;//使用++j是方便下面返回时的判断}else {i = i - j + 2;//若i-j+1则返回至else时的i值，相当于多if一次j = 0;//j从头开始遍历}}if (j > T[0]) {return i - T[0];//}//j>T[0]即表示子串已遍历完全elsereturn 0;
}

2.首尾匹配算法

先比较第一个字符，再比较最后一个字符，最后比较第二至第n个字符，该方法相比第一种只优化了一点，故不详细叙述

3.KMP算法

该算法的本质是利用已经比较过的字符串的相同前缀与后缀，在简单匹配算法的基础上，跳过子串中间的一小串字符来加快匹配速度。

字符串的前缀，若有三个字符串A,B,S,有非空字符串B，使得A=BS（这里的相等指的是BS首尾相连与A完全一致），那么B称A的前缀，S称A的后缀。一个字符串可以有不止一个后缀和前缀。例如字符串“ABDDHSY”，前缀可以有“A”,“ABD”,“ABDD”,“ABDDH”,“ABDDHS”等，但不能是“ABDDHSY”，也不能为“ ”，或“ADD”。

若在一次查找中，子串与主串的指针已经指向了足够的字符，使得已经比较过的字符形成一个字符串，该字符串必然有前缀和后缀。若该字符串的前缀和后缀有相同的几位字符，那么当发现子字符串与主字符串不相等时，使用KMP将直接跳到该字符串的后缀位置进行下一次匹配，而非像BS简单算法一样从该次匹配的下一位开始匹配，若该字符串足够长，这样做无疑会大大减少循环次数。该算法中有一个重点就是next数组，这个数组储存的是主字符串从第一位开始（而非第零位）与自身进行匹配运算字符相同的最大数目。

next数组可以理解为，对主串的每个字符都储存了一个对应的参数，这个参数表示：这个字符前的

 字符串最长相等前后缀的长度+1。同时将第一个字符的最长相等字符串定为-1，第二个值易知为0，因此加一后固定位0和1。

 首先比较主串前i-1个字符和子串前j-1个字符相等，到第i个不等，此时比较主串的第i个字符和子串的第k=next[j]个字符，若相等继续向后比较，若不等继续比较第m=next[k]个字符，以此类推，直到两串字符相同为止。若一直不等，则会匹配到子串的第一个字符，这个字符对应的next值为-1，这种情况直接将主串和子串都向后推一位即可。

 详情：【计算机】数据结构-严蔚敏/清华大学（完）_哔哩哔哩_bilibili本视频来源于网络，如有侵权，请联系删除！免费资料分享、PDF文件获取，请搜索公众号公众号免费分享：考研、考证、四六级、各类大学精品课程【微信公众号：俺要成为科学家】https://www.bilibili.com/video/BV1db411Y7Lm?p=13&spm_id_from=pageDriver第13P

由上面的next思想，知可用递归求next数组

代码实现如下

int KMP(SString S, SString T, int pos) {int i = pos;int j = 1;while (i < S[0] && j < T[0]) {if (j == 0 || S[i] == T[j]) {++i;++j;}elsej = next[j];}if (j < T[0])//子串已匹配完return i - T[0];elsereturn 0;
}

void getnext(SString T, int next[]) {int i = 1;next[1] = 0;int j = 0;while (i < T[0]) {if (j == 0 || T[i] == T[j]) {++i, ++j;next[i] = j;}elsej = next[j];}
}

在有next数组的基础上，可以实现进一步的代码优化。即对于主串，后面的字符设next值为i，若与前面的第i个字符的next值相同，则next值等于前面字符的next值。

代码实现如下

void getnextval(SString T, int nextval[]) {int i = 1;nextval[1] = 0;int j = 0;while (i < T[0]) {if (j == 0 || T[i] == T[j]) {++i, ++j;if (T[i] != T[j])nextval[i] = j;elsenextval[i] = nextval[j];}elsej = nextval[j];}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！