2023年7月20日发(作者：)

串匹配算法前⾔串匹配问题是解决许多应⽤（⽂本编辑器，数据库检索，C++模板匹配，模式识别等等）的重要技术。这个问题有两个输⼊，第⼀个是⽂本（Text），第⼆个是模式（Pattern），⽬的是要在⽂本中寻找模式。通常⽽⾔⽂本要远⼤于模式。T : now is the time for all good people to come （长度为n)P ：people (长度为m)串匹配问题可分为四种类型：detection : P是否出现？location : P⾸次出现在哪⾥？counting : P出现了多少次？enumeration : 各出现在哪⾥？显然，解决location是最重要的，如果监测到了，就表明出现了（detection），出现多少次，只要将未⽐较的字符串根据同样的⽅法求得下⼀次⾸次出现的位置，直到整个⽂本结束，出现在哪⾥只要记录位置做标记即可。下⾯开始介绍串匹配算法。暴⼒匹配思想是⾃左⽽右，以字符为单位，依次移动模式串，直到某个位置发⽣匹配。这个算法最好的情况是第⼀次就⽐对成功，最好情况的上边界则是每次⽐对时，第⼀个字符都不匹配，这样就移动⼀格，最好情况的复杂度就等于Ω(n), n为⽂本的长度。最坏的情况是每次⽐较模式最后⼀个字符的时候才发现不匹配，这样就会导致最坏情况，时间复杂度为O(n⋅m).C++实现版本1：int match(string P, string T) { size_t n = (), i = 0; size_t m = (), j = 0; while (i < n - m + 1 && j < m) //⾃左向右逐次⽐较 if ( T[i] == P[j]) { i++; j++;} // 若匹配，则转到下⼀对字符 else { i -= j - 1; j = 0;} // 否则，T回退，P复位 return i - j;}C++实现版本2：int match(string P, string T) { size_t n = (), i; size_t m = (), j; for ( i = 0; i < n - m + 1; i++) { //T[i]与P[0]对齐 for ( j = 0; j < m; j++) //逐次匹配 if ( T[i+j] != P[j]) break; //失配则转到下⼀位置 if ( m <= j) break; //匹配成功，退出，返回i } return i;}两个实现版本的返回值都是位置信息，当i等于n - m + 1的时候说明未找到模式，否则就是找到了。KMP ：模式记忆暴⼒匹配算法存在着冗余的问题，当最坏情况时，最后⼀个字符匹配失败，模式串和⽂本串的指针都要发⽣回退。KMP算法的原理是利⽤Pattern构建⼀个查询表，根据查询表进⾏来指导移动位数，并且⽂本的索引不需要回退。理解这种算法我推荐阮⼀峰⽼师的（真⼼推荐看看），讲得⾮常清晰，⾮常直观。假设你看过阮⽼师的博客知道原理了，现在来看next表的构建代码:vector buildNext(string P) { //构造模式串P的next表 size_t m = (), j = 0; //“主”串指针 vector N(m, 0); //next表 int t = N[0] = -1; //模式串指针（通配符*） while ( j < m - 1 ) //j是不会减⼩的，j会在循环内变为m-1，此时退出 if ( 0 > t || P[j] == P[t] ) { //当出现通配符也就是0>t, 当前j⾃加1，next表对应j为0。 //当不是通配符时，⽐较是否相等，相等则next表对应j⾃加1 j++; t++; N[j] = t; } else t = N[t]; //失配，根据前⾯得到的next，来看应该从那⾥开始⽐较，⽐如下⾯的匹配等于4的时候，e不等于c，查表知e所在的位置为0，也就是没有相同的前后缀，所以从0开始继续匹配，如果⼤于0，说明有共同前后缀，此时 return N;}这⾥需要注意的⼀点是，阮⼀峰⽼师的博客中当前next表是代表当前j的公共最⼤前后缀的长度，⽽这个实现中当前next表是代表j-1的公共最⼤前后缀的长度。关于t = N[t]可以见下图，当X不匹配Y的时候，此时我们根据next表，由当前next表的值知，P[0, t)和P[j - t, j)是相同的，此时应该移动j-t，也就是从第t位开始⽐较，也就是N(t)的长度。有⼀种特殊情况需要考虑，当N(t)等于0时，此时从0开始⽐较，如果第0位也不等于当前j，根据性质，t此时就等于-1了，此时就进⼊0>t的条件，⾃增j，⾃增t，当前j没有共同前后缀。这⾥开始设N[0]等于-1以及t等于-1，有两层作⽤，第⼀层是为了⾸轮⽐较时，需要隔开⼀位⽐较。第⼆层作⽤是为了防⽌后⾯与第⼀位不相等时，可以根据-1这个条件进⼊if条件，防⽌卡死。很是巧妙。下⾯有⼀个事例：有了next表的构造⽅法，接下来就是根据next表进⾏匹配了。匹配代码如下：int match(string P, string T) { vector next = buildNext(P); size_t n = (), i = 0; size_t m = (), j = 0; while (j < m && i < n) if (0 > j || T[i] == P[j]) { i++; j++;} else j = next[j]; return i - j;}理解了next表的构造原理，其实就理解了匹配过程，next构造过程就是模式串的⾃我匹配。当失配时，如果next表的值⼤于0，说明有公共的前后缀，那么就不需要从0开始⽐较，直接从公共前后缀的后⼀个字符与当前⽂本的第j个字符开始⽐较。KMP再改进考虑下⾯这个情况，明知T[4]不等于P[4]且P[1] = P[2] = P[3] = P[4]，还要⽐对剩余的P[1], P[2], P[3], 这是没有必要的，这是需要改进next表。改进只需要把next中的N[j] = t换成N[j] = ( P[++j] != P[++t] ? t : N[t] )即可。如下所⽰：因为相同，所以可以直接跳过他们，更快。KMP算法的时间复杂度是O(m+n), 空间复杂度是O(m+n). 匹配过程令k = 2i- j，k每次循环⾄少加1，判断为真则i加1，判断为假，j⾄少减1，所以k <= 2n - 1; 同理next过程也是如此。KMP⼩结：以判断公共前后缀来进⾏模式串的移动，有公共前后缀，移动到前缀的下⼀位即可，没有公共前后缀则移动到头部。通过通配符来有效构造next表，表的第⼀位为-1，当第⼀位对齐不相等的时候，这时通配符匹配，使⽂本串（也包括模式串的⾃我匹配）可以移动起来，不⾄于卡死。当发⽣重复串的时候，跳过他们，不进⾏⽐较。BM算法对于BM算法的介绍，我同样推荐看阮⼀峰⽼师的（真⼼推荐看看），讲的⼗分清楚。同样假设你看过博客知道原理了，就知道BM算法有两个next表，⼀个是坏字符（bad character）bc表，另⼀个是好后缀（good suffix）gs表，现在来看看如何构造这两个表。bc表对于坏字符表，构造起来很简单，它是记录模式串中每种字符最后出现的位置，代码如下：vector buildBC(string P){ vector bc(256, -1); for(size_t m = (), j = 0; j < m; j++) bc[ P[j] ] = j; return bc;}坏字符移动规则： 后移位数 = 坏字符的位置- 搜索词中的上⼀次出现位置基于BM-DC的算法最好情况就是O(n/m), 最坏情况是O(m∗n)。最好情况：最坏情况：gs表相⽐于bc表，gs表就很不好构造了。⾸先来看看⼀个概念，最⼤匹配后缀长度表，通过它来构建ss（suffix size)表，然后通过ss表来构造gs表。最⼤匹配后缀长度的意思是在P[0,j)的所有缀中，与P的某⼀后缀匹配最长者。例如下⾯的P[0, 3) = ICE, 与末尾的ICE最长匹配，则P[0, 3)的末尾就为最长匹配长度3，RICE同理。（ss表的值就等于最⼤匹配长度）ss表末尾的值就是整个模式串的长度，简单的想法是遍历每⼀个字符向后递减，与后缀开始⼀⼀⽐较(暴⼒搜索），这样做的复杂度为O(m2), 很好的做法是下⾯的代码（从后往前遍历），时间复杂度只有O(m)。vector buildSS ( string P ) { //构造最⼤匹配后缀长度表：O(m) int m = ();

vector ss(m, 0); //Suffix Size表 ss[m - 1] = m; //对最后⼀个字符⽽⾔，与之匹配的最长后缀就是整个P串// 以下，从倒数第⼆个字符起⾃右向左扫描P，依次计算出ss[]其余各项 for ( int lo = m - 1, hi = m - 1, j = lo - 1; j >= 0; j -- ) if ( ( lo < j ) && ( ss[m - hi + j - 1] <= j - lo ) ) //情况⼀：该情况处于最⼤匹配后缀后的字符，例如，RICE中的R,I,C. ss[j] = ss[m - hi + j - 1]; //直接利⽤此前已计算出的ss[] else { //情况⼆: 遇到匹配项，依次递减进⾏匹配 hi = j; lo = min ( lo, hi ); while ( ( 0 <= lo ) && ( P[lo] == P[m - hi + lo - 1] ) )

Processing math: 100% lo--; //逐个对⽐处于(lo, hi]前端的字符 ss[j] = hi - lo; // ⾼位减去递减后的低位，得到最长匹配长度 } return ss;}知道ss表后，gs表可有ss表推导出，有两种情况：对应的代码如下：vector buildGS ( string P ) { //构造好后缀位移量表：O(m) vector ss = buildSS ( P ); //Suffix Size表 size_t m = ();

vector gs(m, m); //Good Suffix shift table for ( size_t i = 0, j = m - 1; j < UINT_MAX; j -- ) //逆向逐⼀扫描各字符P[j] if ( j + 1 == ss[j] ) //若P[0, j] = P[m - j - 1, m)，则 while ( i < m - j - 1 ) //对于P[m - j - 1]左侧的每个字符P[i]⽽⾔ gs[i++] = m - j - 1; //m - j - 1都是gs[i]的⼀种选择 for ( size_t j = 0; j < m - 1; j ++ ) //正向扫描P[]各字符，gs[j]不断递减，直⾄最⼩ gs[m - ss[j] - 1] = m - j - 1; //m - j - 1必是其gs[m - ss[j] - 1]值的⼀种选择 return gs;}BM_BC+GS知道了bc表和gs表，接下来就是匹配过程了，与阮⽼师的博客上说的⼀致，取两个表的最⼤值。代码如下：int match ( string P, string T ) { //Boyer-Morre算法（完全版，兼顾Bad Character与Good Suffix） vector bc = buildBC ( P ), gs = buildGS ( P ); //构造BC表和GS表 size_t i = 0; //模式串相对于⽂本串的起始位置（初始时与⽂本串左对齐） while ( () >= i + () ) { //不断右移（距离可能不⽌⼀个字符）模式串 int j = () - 1; //从模式串最末尾的字符开始 while ( P[j] == T[i + j] ) //⾃右向左⽐对 if ( 0 > --j ) break;

if ( 0 > j ) //若极⼤匹配后缀 == 整个模式串（说明已经完全匹配） break; //返回匹配位置 else //否则，适当地移动模式串 i += max ( gs[j], j - bc[ T[i + j] ] ); //位移量根据BC表和GS表选择⼤者 } return i;}基于BM_BC+GS算法最好情况是O(n/m)，最坏情况由于有了gs表，变为了O(m+n).综合性能各种模式匹配算法的时间复杂度如下所⽰：参考