数据结构与算法 11. 串 2021-07-28 浏览量 1395 暂无评论 [TOC] ## 11.1 ADT ### 术语 $S[0, n)$ 子串:$S.substr(i, k) = S[i, i + k)$ 前缀:$S.prefix(k) = S.substr(0, k) = S[0, k)$ 后缀:$S.suffix(k) = S.substr(n - k, k) = S[n - k, n)$ ## 11.2 串匹配 `grep `正则匹配字符串 模式匹配不同的难度: - detection - **location** - counting - enumeration ### 如何评测性能 不能随机采样P和T来评测,因为在随机采样的情况下,匹配成功的概率超低。 随机T,对成功、失败的匹配分别测试 成功:在T中,随机取出长度为m的子串作为P,分析平均复杂度 失败:随机P,统计平均复杂度 ## 11.3 蛮力匹配 版本1 ```cpp int match(char *P, char * T) { size_t n = strlen(T), i = 0; size_t m = strlen(P), j = 0; while (j < m && i < n) { if (P[j] == T[i]) {i++; j++} else {i -= j - 1; j = 0} return i - j; } // 若i - j > n - m,则失败,因为已经超过了可能匹配到的最大下界 ``` 版本2 ```cpp int match(char *P, char * T) { size_t n = strlen(T), i = 0; size_t m = strlen(P), j; for (i = 0; i < n -m + 1; i++) { for (j = 0; j < m; j++) if (T[i+j] != P[j]) break; if (m <= j) break; } return i; } ``` 复杂度:$O(n * m)$ 缺点: - 不能避免局部匹配 当字母表越大时,蛮力算法的期望复杂度为线性,因为每次只需常数次比较。 ## 11.4 KMP算法:从记忆力到预知力 在当前字符匹配失败时,之前的字符都是匹配成功的,充分利用这一信息 ### next[]表 自匹配 = 快速右移 长度为t的前缀与长度为t的后缀完全匹配。 每次选取这个集合中最大的t,避免回溯。 在当前字符不匹配时,通过查表得到下一次比对开始的地方,之所以可以从这个地方开始,是因为通过这样的移动,前t个位置已经匹配,即在之前已匹配的串中,存在长度为t的相等前后缀。移动的大小为j - t。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/5dc160f9048c401faf497ed791e2e0eb.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/2d4eb019ccc046dfb48c9bbd87d0350d.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 统一将next[]表中的第0项置为-1,作为通配哨兵前缀(第0个字符匹配失败,取P[-1]也就是通配符来匹配,接下来,P和T都移到下一位)。 ### 构造next[]表 看next[j]与当前需要比对的字符是否相等,相等则next[j++] = next[j] + 1,否则,取next[next[j]]再比对,直到相等,其中的含义即当前所匹配的相等前后缀子串必然包含在此前已匹配的串中。 ```cpp int* buildNext(char* P) { size_t m = strlen(P), j = 0; int* N = new int[m]; int t = N[0] = -1; while (j < m - 1) if ( 0 > t || P[j] == P[t]) N[++j] = ++t; else t = N[t]; return N; } ``` 为什么可以跳过前i个,是因为以它们开头的字符串都不可能与已P[0, t)开头的字符串匹配,因为匹配到T[i]时,就不匹配了,所以才会有跳过这一步。 复杂度:$O(n)$ ### 缺陷 当模式串中包含连续重复字符时,退化为逐步前进 ![在这里插入图片描述](https://img-blog.csdnimg.cn/f4550e7fbd3a47a6aa2174c9b2eca27e.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp int* buildNext(char* P) { size_t m = strlen(P), j = 0; int* N = new int[m]; int t = N[0] = -1; while (j < m - 1) if ( 0 > t || P[j] == P[t]) j++; t++; N[j] = P[j] != P[t] ? t : N[t]; else t = N[t]; return N; } ``` ## 11.5 BM_BC算法:坏字符 ### 不对称性 利用串匹配的特性:多个字符对多个字符 判断串是否相等与是否不等的成本不同。 ### 前轻后重 优先比对靠后的元素,因为如果靠后的元素失配,那么将模式串移到当前匹配失败字符的下一位 跳过的条件:当前匹配的字符不在模式串内 如果当前匹配失败,并且当前匹配的字符在模式串中,则将模式串中的该字符与其对其 ![在这里插入图片描述](https://img-blog.csdnimg.cn/ce9a20975897426893e7aa2da5525a62.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 构造bc[] ```cpp int* buildBC(char* P) { int* BC = new int[256]; for (int i = 0; i < 256; i++) BC[i] = -1; for (size_t m = strlen(P), j = 0; j < m; j++) BC[P[j]] = j; return BC; } ``` ### 实现 ```cpp int BMBC(char* P, char* T) { int* BC = buildBC(P); int i = strlen(P) - 1, j = strlen(P) - 1; while (i < strlen(T)) { if (T[i] == P[j]) { i--; j--; } else { if (BC[T[i] == -1) { i += strlen(P) - 1; j = strlen(P) - 1; } else if ((j - BC[T[i]]) < 0) { i += strlen(P) - j; j = strlen(P) - 1; } else { i += strlen(P) - BC[T[i]] - 1; j = strlen(P) - 1; } } } } ``` ### 性能分析 最好:$O(n / m)$ 最坏:$O(n * m)$ 后m-1个字符都匹配,第1个字符不匹配,没有利用好经验。 ## 11.6 BM_GS算法:好后缀 疑问:如果匹配的后缀是重复元素还能省掉中间两趟吗? ![在这里插入图片描述](https://img-blog.csdnimg.cn/f565169d93e54f448dc8870c629f2f56.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 记录当前匹配的好后缀,下次移动时,将模式串中的好后缀与其对齐,和KMP有啥本质的区别? KMP是前后缀,GS可以在模式串中,不一定是前缀 ### 构造 ### BM性能 综合bc和gs 最好:$O(n / m)$ 最差:$O(m + n)$ ![在这里插入图片描述](https://img-blog.csdnimg.cn/2fa9163556bc489f8b02b022be7459ff.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 11.7 Karp-Rabin算法:串即是数 如果能把串变成数,那每次只需要常数次比较 每个有限维的自然数向量,唯一对应于一个自然数。 $ ~ p(1)^{1+a_1} \times p(2)^{1+a_2} \times ... \times p(n)^{1+a_n}$ 其中$p(k)$代表第k个素数。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/c6be90128d344eca89101e94b5405ba8.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 这个数太大了,无法正常存储吧 ### 串亦是数 字符在字母表中的编号 ![在这里插入图片描述](https://img-blog.csdnimg.cn/aafc9d6bc0eb444abe95bb7ad33cf9ff.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 散列 想用指纹(数字)来表示串的话,如果直接转换成对应进制的数字,则位数太高,甚至超过64位(8字节),这样不仅储存不便,比较也不便 **散列压缩** **散列冲突** 两个不同的元素在散列变换后,有可能被映射到同一个散列码,那么再进行严格比对。 **快速指纹计算** 相邻的两个指纹之间,有着某种相关性,理论上可在$O(1)$的时间内,由上一指纹得到下一指纹。 赞赏 微信支付 支付宝支付