本文共 4076 字，大约阅读时间需要 13 分钟。
该算法主要利用坏字符规则和好后缀规则进行转换。所谓坏字符规则，是指不能匹配时的字符在待匹配字串中从右边数的位置；而好后缀规则则是指子串中从该不匹配位置后面所有字符（都是已匹配字符）再次在字串中出现的位置(k)，其中s[k,k+1,—,k+len-j-1] = s[j+1, j+1,—,len-1], 并且s[k-1] != [j] || s[k-1] = $, 其中$表示增补的字符，可以与任何字符相等。
#include#include #include using namespace std;#define SIZE 256 //字符集字符数void generateBadChar(char *b, int m, int *badchar)//(模式串字符b，模式串长度m，模式串的哈希表){ int i, ascii; for(i = 0; i < SIZE; ++i) { badchar[i] = -1;//哈希表初始化为-1 } for(i = 0; i < m; ++i) { ascii = int(b[i]); //计算字符的ASCII值 badchar[ascii] = i;//重复字符被覆盖，记录的是最后出现的该字符的位置 }}void generateGS(char *b, int m, int *suffix, bool *prefix)//预处理模式串，填充suffix，prefix{ int i, j, k; for(i = 0; i < m; ++i)//两个数组初始化 { suffix[i] = -1; prefix[i] = false; } for(i = 0; i < m-1; ++i)//b[0,i] { j = i; k = 0;//公共后缀子串长度(模式串尾部取k个出来，分别比较) while(j >= 0 && b[j] == b[m-1-k])//与b[0,m-1]求公共后缀子串 { --j; ++k; suffix[k] = j+1; //相同后缀子串长度为k时，该子串在b[0,i]中的起始下标 // (如果有多个相同长度的子串，被赋值覆盖，存较大的) } if(j == -1)//查找到模式串的头部了 prefix[k] = true;//如果公共后缀子串也是模式串的前缀子串 }}int moveByGS(int j, int m, int *suffix, bool *prefix)//传入的j是坏字符对应的模式串中的字符下标{ int k = m - 1 - j;//好后缀长度 if(suffix[k] != -1)//case1，找到跟好后缀一样的模式子串（多个的话，存的靠后的那个（子串起始下标）） return j - suffix[k] + 1; for(int r = j + 2; r < m; ++r)//case2 { if(prefix[m-r] == true)//m-r是好后缀的子串的长度，如果这个好后缀的子串是模式串的前缀子串 return r;//在上面没有找到相同的好后缀下，移动r位，对齐前缀到好后缀 } return m;//case3,都没有匹配的，移动m位（模式串长度）}int str_bm(char *a, int n, char *b, int m)//a表示主串，长n; b表示模式串,长m{ int *badchar = new int [SIZE];//记录模式串中每个字符最后出现的位置 generateBadChar(b,m,badchar); //构建坏字符哈希表 int *suffix = new int [m]; bool *prefix = new bool [m]; generateGS(b, m, suffix, prefix); //预处理模式串，填充suffix，prefix int i = 0, j, moveLen1, moveLen2;//j表示主串与模式串匹配的第一个字符 while(i < n-m+1) { for(j = m -1; j >= 0; --j) //模式串从后往前匹配 { if(a[i+j] != b[j]) break; //坏字符对应模式串中的下标是j } if(j < 0) //匹配成功 { delete [] badchar; delete [] suffix; delete [] prefix; return i; //返回主串与模式串第一个匹配的字符的位置 } //这里等同于将模式串往后滑动 j-badchar[int(a[i+j])] 位 moveLen1 = j - badchar[int(a[i+j])];//按照坏字符规则移动距离 moveLen2 = 0; if(j < m-1)//如果有好后缀的话 { moveLen2 = moveByGS(j,m,suffix,prefix);//按照好后缀规则移动距离 } i = i + max(moveLen1,moveLen2);//取大的移动 } delete [] badchar; delete [] suffix; delete [] prefix; return -1;}int main(){ string a = "abcacabcbcbacabc", b = "cbacabc"; cout << a << "中第一次出现" << b << "的位置(从0开始)是：" << str_bm(&a[0],a.size(),&b[0],b.size()); return 0;}
原文链接
https://blog.csdn.net/qq_21201267/article/details/92799488?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase
5、RK算法
Rk算法全称：Rabin-Karp算法，是由两位发明者Rabin和Karp的名字来命名，它其实就是BF算法的升级版。 BF算法的时间复杂度O(n*m)是因为在极端情况下子串和模式串需要比对每一个字符，所以可以对BF算法进行改造一下，引入hash算法时间复杂度就会立马降低。RK算法思路：
通过hash算法堆主串中的n-m+1个子串分别求hash值，然后逐个与模式串的hash值比较大小，在不考虑hash冲突的前提下，只要子串的hash值跟模式串的hash值相等，那就说明子串和模式串是匹配的。Hash值是一个数字，数字之间的比较时非常快速的，这样依赖模式串跟子串的比较不再是一个个字符的比较，而是粗粒度hash值比较即可，比较效率就大大提高了。 但问题是，子串hash值的计算是一个低效的过程，这个过程需要遍历子串中的每个字符。因此整体RK算法效率并没有提高，要想真正提高RK算法的效率，这个问题就必须解决，即想办法提高计算子串hash值得效率，也就是计算子串hash值得哈希算法的设计问题。如果选择的素数q>=m, 则RK算法的期望运行时间为O（n+m）, 如果m<<n，则算法的期望运行时间为O(n)。
#include#include #include #define q 144451#define d 26 using namespace std; int RK(const string &T,const string &P){ int m=T.length(),n=P.length(); unsigned int h=1, t=0, p=0; for(int i=0;i
详解原文
https://blog.csdn.net/pcwl1206/article/details/86673675?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-2#2%E3%80%81RK%20%E7%AE%97%E6%B3%95