数据结构与算法——串匹配（C++）数据结构及实现

文章目录

1 串匹配概述
2 蛮力算法

2.1 蛮力算法版本A
2.2 蛮力算法版本B
2.3 蛮力算法测试

3 KMP算法

3.1 KMP主算法
3.2 构造next表
3.3 KMP算法测试程序

4 BM算法

4.1 BM主算法
4.2 坏字符策略与bc表
4.3 好后缀策略与gs表
4.4 BM算法测试

5 Karp-Rabin算法
6 Sunday算法
参考材料

1 串匹配概述字符串匹配有多种形式，包括模式检测( pattern detection)，模式定位(pattern location)，模式计数(pattern counting)，模式枚举(pattern enumration)。
2 蛮力算法蛮力算法是最直接最直觉的方法，可以作为改进的基础。
2.1 蛮力算法版本A

//brute-force-A.h #include int matchA( char* P, char* T ){//串匹配算法（Brute-force-1) size_t n = strlen( T ), i = 0; size_t m = strlen( P ), j = 0; while ( j < m && i < n ) if( T[i] == P[j] )//匹配则转到下一个字符 { ++i; ++j; } else{//不匹配则文本串回退,模式串复位 i -= j - 1; j = 0; } return i - j; }

2.2 蛮力算法版本B

//brute-force-B.h #include int matchB( char* P, char* T ){//串匹配算法（Brute-force-2) size_t n = strlen( T ), i = 0; size_t m = strlen( P ), j ; for( i = 0; i < n - m + 1; ++i ){//文本串从第i个字符开始逐个比对 for( j = 0; j < m; ++j){ if( T[i + j] != P[j] ) break; //失配则右移再做一轮比对 } if( j >= m ) break; //找到匹配子串 } return i; }

2.3 蛮力算法测试 【数据结构与算法——串匹配（C++）】蛮力算法的测试程序如下，可见匹配成功时，版本A与版本B都会返回模式串在文本串中的位置。串匹配失败时，版本1返回大于n-m，版本2返回n-m+1。

/* * test program on string matching * author@Ripples * 20200807 */ #include "brute-force-A.h" #include "brute-force-B.h" #include using namespace std; int main(){ //初始化模式串与文本串 char P[] ="structure"; char Y[] ="alo"; char T[] ="data structure and algorithm"; //测试brute-force-1 cout << matchA( Y, T ) << endl; //28 返回大于n-m表示失败 cout << matchA( P, T) << endl; //5 P在T中的位置//测试brute-force-2 cout << matchB( Y, T ) << endl; //26 返回n-m+1 表示匹配失败 cout << matchB( P, T) << endl; //5 P在T中的位置return 0; }

3 KMP算法 3.1 KMP主算法 KMP算法可以视为从蛮力算法的版本A改进而来，KMP算法的思路可以总结如下：
（1）T[ i ] == P[ j ] ，则++i, ++j ，继续匹配；
（2）T[ i ] != P[ j ]，i不变，j = next[ j ]。
其中，next表示KMP算法赖以高效实现的核心。KMP算法主算法如下所示

//match_kmp.h #include int matchKMP( char* P, char* T ){//串匹配算法（Brute-force-1) int* next = buildNext( P ); int n = strlen( T ), i = 0; int m = strlen( P ), j = 0; while ( j < m && i < n ) if( 0 > j || T[i] == P[j] )//匹配则转到下一个字符 { ++i; ++j; } else{//不匹配则文本串回退,模式串复位 j = next[ j ]; } delete [] next; return i - j; }

3.2 构造next表 next表各值的含义是：当前字符以前的字符串中，有多大长度相同前缀与后缀。
求解next表只与模式串有关，具体求解方式如下：
（1）P[ k ] == P[ j ]（其中k = next[ j ]），next[ j + 1 ] = next[ j ] + 1
（2）P[ k ] != P[ j ]（其中k = next[ j ]），next[ j + 1 ] = next[ k ] + 1= next[ next[ j ] ] + 1
next表构造算法优化
不允许P[ next[ j ] ] == P[ j ]，以此避免重复比较以及失配的字符。next表构造算法如下

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] ); //N[j] =t }else{//失配 t = N[t]; } } return N; }

3.3 KMP算法测试程序以下是KMP算法的测试程序，可以看出KMP完成了串匹配的任务。

/* * test program on string matching * author@Ripples * 20200807 */ #include "match_kmp.h" #include using namespace std; int main(){ //初始化模式串与文本串 char P[] ="structure"; char T[] ="data structure and algorithm"; cout << matchKMP( P, T ) << endl; //5 return 0; }

4 BM算法 4.1 BM主算法 BM算法与KMP算法类似。不同的是，BM算法从后往前匹配，充分使用以往的比对信息使得模式串往后移动尽可能远的距离。
BM算法分别用了坏字符策略与好后缀策略，对应bc表与gs表。通过这两种策略，完成了对以往比对信息的充分利用。

#include int matchBM( char* P, char* T ){ int* bc = buildBC( P ); int* gs = buildGS( P ); //构造bc表与gs表 size_t i = 0; while( strlen( T ) >= i + strlen( P )){ int j = strlen( P ) - 1; while( P[j] == T[i+j]) if( 0 > --j) break; if( 0 > j ) break; else i += (( gs[j] > ( j - bc[ T[i+j]])) ? gs[j] : ( j - bc[ T[i+j]])); //选择两者中的更大者 } delete [] gs; delete [] bc; return i; }

4.2 坏字符策略与bc表坏字符策略：某个字符不匹配，模式串向右移动坏字符位置 - 坏字符在模式串中出现的最右边位置。其中，坏字符表示的是文本串中不匹配的字符。

//建立bc表 int* buildBC ( char* P ) { //构造Bad Charactor Shift表：O(m + 256) int* bc = new int[256]; //BC表，与字符表等长 for ( size_t j = 0; j < 256; j ++ ) bc[j] = -1; //初始化：首先假设所有字符均未在P中出现 for ( size_t m = strlen ( P ), j = 0; j < m; j ++ ) //自左向右扫描模式串P bc[ P[j] ] = j; //将字符P[j]的BC项更新为j（单调递增）——画家算法 return bc; }

4.3 好后缀策略与gs表好后缀策略：字符失配时，后移位数等于好后缀位置 - 好后缀上一次出现位置。
gs表的建立依托于ss表的建立，建表程序如下所示。

//建立ss表 int* buildSS ( char* P ) { //构造最大匹配后缀长度表：O(m) int m = strlen ( P ); int* ss = new int[m]; //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 ) ) //情况一 ss[j] =ss[m - hi + j - 1]; //直接利用此前已计算出的ss[] else { //情况二 hi = j; lo = ( lo < hi ) ? lo : hi; while ( ( 0 <= lo ) && ( P[lo] == P[m - hi + lo - 1] ) ) //二重循环？ lo--; //逐个对比处于(lo, hi]前端的字符 ss[j] = hi - lo; } return ss; } //建立gs表 int* buildGS ( char* P ) { //构造好后缀位移量表：O(m) int* ss = buildSS ( P ); //Suffix Size table size_t m = strlen ( P ); int* gs = new int[m]; //Good Suffix shift table for ( size_t j = 0; j < m; j ++ ) gs[j] = m; //初始化 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]值的一种选择 delete [] ss; return gs; }

4.4 BM算法测试以下是BM算法的测试程序，可以看出BM完成了串匹配的任务。

/* * test program on string matching * author@Ripples * 20200807 */ #include "match_bm.h" #include using namespace std; int main(){ //初始化模式串与文本串 char P[] ="structure"; char T[] ="data structure and algorithm"; cout << matchBM( P, T ) << endl; //5 return 0; }

5 Karp-Rabin算法 Karp-Rabin算法遵循“万物皆数”的中心思想，将字符串转换为散列码，称其为“指纹”。“判断模式串P是否与文本串T匹配”这一问题可以转换为“判断T中是否有某个子串与模式串P拥有相同的指纹”。
Karp-Rabin算法具体的流程如下：