Loading... # 串 ## 基本概念 串是零个或多个字符的有限序列。显然，串是一种线性表。显然，串是一种线性表。串中任意多个国家统计局的字符组成的子序列称为该串的子串，特别地，空串是任何串的子串。任意串S都是自身的子串，除S本身以外的S的其他子串为S的真子串。 串的存储：顺序存储与紧缩顺序存储。还有不必移动内存块的链接存储。 ## 串运算 CMyString.h ```c #define MAX_STRING_SIZE 1024 struct cMyString { int length; char str[MAX_STRING_SIZE+1] }; typedef struct cMyString CMyString; void InitCMyString(CMyString *, char *s); /*初始化函数，构造一个字符指针所指的串*/ void Concatenate(CMyString *, CMyString *s); /*将字符串s附加到本字符串之后*/ void InsertS(CMyString *, int pos, CMyString *s); /*将字符串s插入到本字符串pos所指的位置*/ void DeleteS(CMyString *, int pos, int len); /*删除从pos起的连续len个字符*/ CMyString SubString(CMyString *, const int pos, const int len); /*提取一个字符串，从pos位置起长度为len的字符*/ char *GetString(CMyString *); /*获取本字符串*/ int Find(CMyString *, CMyString *s); /*查找字符串s首次出现的位置，如果不包含s则返回0*/ ``` ## 模式匹配 ### 朴素的模式匹配 挨个比较，不对后移再挨个比较。 ### KMP匹配算法 ** 一知半解**，不知道为什么 简单而言： KMP 算法借助于一个辅助数组next，来确定当匹配过程中出现不等时，P右移的位数和开始比较的字符位置。在这个数组中，next[i]的取值只与P的前i+1个字符本身相关，而与目标T无关。在匹配过程中，一旦遇到$p_j$和$t_j$比较时不相等，则∶若 $next[i] \ge 0$，应将P右移i-next[i]个字符，用P中第 next[i]个字符与$t_j$进行比较;若next[i]=-1，P中任何字符都不必再与t;比较，而应将 P右移i十1个字符，从$p_0$和$t_{j+1}$开始重新进行下一趟比较。 一旦计算出与P相关的next数组，则基于next数组的上述含义，可以很容易地给出串的匹配算法。 ```c int Find(CMyString *CS, CMyString *s){ int i, j, *next = (int *)malloc(sizeof(int) * s->length); /*构造模式s的next数组，详见下面的求next数组的算法*/ GenKMPNext(next, s); for(i=0,j=0;i<s->length&&j<CS->Length){ if (s->str[i]==CS->str[j])/*相等*/ {i++;j++;} else if(next[i]>=0)/*不相等且next[i]>=0*/ i=next[i];/*i减少j-i变大，右移*/ else {i=0;j++;}/*同上*/ } if(i>=s->length) return j-s->length;/*匹配成功，返回子串的起始位置*/ else return -1;/*匹配失败，返回-1*/ } ``` * 注意，在匹配算法中，右移位数是由$p_i$与$t_j$共同决定的，j-i的值即为$p_0$的位置，所以比较前后的j-i可知移位多少。 next数组的计算方法 ```c void GenKMPNext(int *next, CmyString *s) { int i=0,j=-1; next[0] = -1; while(i<s->length-1) { /*找出p0,p1....pi中最大的相同的最左端子串和最右端子串*/ while (j>=0&&s->str[i]!=s->str[j]) j=next[j]; i++;j++; if(s->str[i]==s->str[j]) next[i]=next[j]; else next[i]=j; } } ``` 算法效率分析： 算法效率分析∶ 记 P 的长度为m，目标 T 的长度为n，则 KMP 匹配算法的时间复杂性分析如下∶整个匹配算法由 Find()和 GenKMPNext()两个部分的算法组成。在 Find())中包含一个循环，j的初值为0，每循环一次j的值严格增加1，直到j等于n 时循环结束，故循环执行了 n 次。在GenKMPNext()中，表面上有两重循环，时间复杂性似乎为O(m²)，其实不然，GenKMPNext()的外层循环恰好执行 m—1次;另外，j的初值为-1，外层循环中每循环一次，j的值增加1，同时，在内层循环中j被减小，但最小不会小于一1，因此，内层循环中j=next[j]语句的总的执行次数应小于或等于j的值在外层循环中被增加1 的次数，亦即在算法GenKMPNext()结束时，j=next[j]被执行的总次数小于等于 m-1次。 综上所述，对于长度为 m 的模式P和长度为n 的目标 T的模式匹配，KMP算法的时间复杂性为 O(m+n)。 ### BM匹配算法 **也没太看懂** 由一个数组变成了两个，同时从右向左比较。 以模式P="at_that"为例，其长度m=7，BM匹配算法中的第1个数组是*delta1*，该数组指出字符集中的每个字符在模式中相对于最右端的距离，用*代表任何一个未出现在模式中的字符，则对于给定的模式P，有∶ P|*|a|t|_|t|h|a|t| --|--|--|--|--|--|--|--|--| delta1|7|1|0|4|0|2|1| 首先令delta2[7]=1，对于任意的k=6,5,...,2,1，考虑子串$s=p_{k+1}p_{k+2} \cdots p_7$(即$p_k$右边的子串，而不是从$p_k$算起)，相对于模式而言依次向左移动子串s，如果子串s没有匹配上，则继续向左移动子串s，直到匹配或者无法匹配（s的最左端字符移出到模式的最左端），记匹配或者无法继续匹配之前子串s移动的位数为n，则：delta2[k]=7-k+n P|a|t|_|t|h|a|t| --|--|--|--|--|--|--|--| delta2|7|7|7|7|6|3|1| 匹配时，首先将模式和目标左对齐，从模式最右端开始向左比较，匹配过程中，一旦$p_i$和$t_j$不相等，计算k=max(delta[ t[j] ], delta2[i])，并将P右移k+i-m位(m为模式串的长度)，用$p_m$和$t_{j+k}$继续比较。 Last modification：January 11, 2023 © Allow specification reprint Like 如果觉得我的文章对你有用，请留下评论。