KMP.zip_DNA_KMP算法

#include <algorithm> #include <string> #include <iostream> using namespace std; #define SIZE 256 //字符集字符数 //生成坏字符表 void generateBadChar(char *b, int m, int *badchar)//(模式串字符b，模式串长度m，模式串的坏字符表) { int i, asc; for(i = 0; i < SIZE; ++i) { badchar[i] = -1;//初始化坏字符表为-1 } for(i = 0; i < m; ++i) { asc = int(b[i]); //计算字符的ASCII值，储存数据信息 badchar[asc] = 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);//按照好后缀规则移动距离 } if(moveLen1>moveLen2) i = i + moveLen1;//取大的移动 else i=i+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; }