数据结构与算法之字符串: PM

2023-03-27 04:20| 来源: 网络整理| 查看: 265

字符串字符串是一个很有意思的结构：由一连串字符的东西排成了一个线性序列它的特点可以归纳为两个方面相比于向量可以存储复杂的结构，字符串里面的元素只能是字符它是一个整体，一般很长，通过整体或局部整体性进行计算经常从里面挑出一段，我们称之为pattern，访问方式是 call-by-pattern这个模式，里面蕴含诸多技巧 PM: Preliminaries 预备知识既然是线性序列，我们就可以把它排个队，通过下标来访问(或通过一个秩的东西来访问，一个意思) 下标从0~n-1, 假设在n的位置有一个虚拟的哨兵，我们叫界桩，同样在处理的时候在-1的位置也有一个哨兵通过这种方式来帮助我们理解一些算法实现字符串还有一个概念叫做substr, 也就是它的局部, 一般它有由两个东西来的定义，i，k S.substr(i,k) = S[i, i+k], 0 if(T[i] == P[j]) { // 若匹配则转到下一对字符 i ++; j ++; } else { // 否则，T回退，P复位 i -= j-1; // 注意这里每个时刻i和j的差都是i-j, 移动一格就是i-j+1，写法不同，意义相同 j = 0; } } return i-j; // 如何通过返回值，判断匹配结果：最后出格，通过判断i-j在允许的范围内 }

算法实现：版本2

int match(char * P, char * T) { size_t n = strlen(T), i = 0; size_t m = strlen(P), j; for(i=0; i if(T[i+j] != P[j]) { break; // 失配，转下一对齐位置 } } if(m int * next = buildNext(P); // 构造一个查询表 int n = (int) strlen(T), i=0; int m = (int) strlen(P), j=0; while(j i++; j++; } else { j = next[j]; } } delete [] next; return i - j; }

直观的对比

在这里插入图片描述

只有绿色和红色部分花时间，最坏情况下也是线性的算法青色的部分被KMP跳过去了, 灰色的部分并没有出现总的时间复杂度不超过O(n) PM: KMP: Understanding next[] 理解查询表

在这里插入图片描述

在某个位置上对齐之后，我们经过一系列的成功，在Y的位置和主串的X适配之后，我们需要胆子大一些快速的滑动，能滑动多少我们不知道，但是我们知道前面多一截的P[0,t)不用考虑，接下来的计算是通过Z替代Y继续和主串的X适配为什么我们可以不用顾及P[0,t), 因为我们可以判定可以不用顾及因为P[0,t)与主串上的P[j-t, j)完全一致，也就是说如果当时失败在j的位置那么在比j小的t的前缀，和某个t长度的后缀它们是相等的，只有这种情况下移动相应的距离，残留下来长度为t的前缀才会和那个后缀相逢它们之间的比较就可以省下来 PM: KMP: Constructing next[] 构造表

在这里插入图片描述

这里我们用到递增的策略，任何一个Pattern串给定之后，我们可以首先把0项字符对应的查询表记录为-1，如上面的M头上记录-1，递增的意义是逐个字符处理以next[0]为基础算next[1],然后算next[2],next[3]…这种基于一个基础，接下来算下一个，再算下一个…我们称为递增的策略假如这个next[]表已经算到第j项了，接下来计算第j+1项我们的核心问题是在第j项之前算到第j+1项，解决这么一个通用的问题所有问题反复借用即可

构造算法

int * buildNext(char * P) { size_t m = strlen(P), j = 0; int *N = new int[m]; int t = N[0] = -1; while(j

【本文地址】

公司简介

联系我们