1 #include <iostream>  2 #include <string.h>  3 #include <stdlib.h>  4   5 using namespace std;  6 //字符串匹配算法，普通的双字符扫描算法不多讲效率很慢O(m*n)的复杂度  7 //下面主要讲述的KMP算法和BM算法  8 //http://www.searchtb.com/2011/07/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E9%82%A3%E4%BA%9B%E4%BA%8B%EF%BC%88%E4%B8%80%EF%BC%89.html  9  10 //KMP算法；http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 11 //此方法主要利用了已经搜索过的字符串的位置信息，利用被搜索的字符串的字符出现位置规律 12 //时间复杂度O(m+n) 13  14 void getNext(string p,int *next){ 15     int len=p.length(),i=0,k=-1; 16     if(len<=0) return; 17     next[i]=-1; 18      19     while(i<len-1){ 20         if(k==-1||p[i]==p[k]){//p[k]表示前缀，p[i]表示后缀  21             k++; 22             i++; 23             if(p[i]!=p[k])  24                 next[i]=k;//若只有这一行，则会做很多无用功 25             else  26                 next[i]=next[k];//因为不能出现p[i] = p[ next[i ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]   27         } else { 28             k=next[k]; 29         } 30     } 31 } 32  33 int kmp_search(string s,string p,int *next){ 34     int sLen=s.length(),pLen=p.length(); 35     if(sLen<=0||pLen<=0) return -1; 36  37     int i=0,j=0; 38     while(i<sLen&&j<pLen){ 39         if(j==-1||s[i]==p[j]){ 40             i++; 41             j++; 42         } else if(s[i]!=p[j]) { 43             j=next[j]; 44         } 45     } 46     if(j==pLen) return i-j; 47     return -1; 48 } 49  50  51 //BM算法 http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html 52 //http://www.cnblogs.com/a180285/archive/2011/12/15/BM_algorithm.html 53 //此方法从被搜索字符串的最后一个位置来比较字符串，当失配时候，可以根据失配位置和被搜索字符串本身省去无效回溯。要比KMP算法更快 54 //坏字符规则 好后缀规则  55 //最好情况下的时间复杂度为O(n/m)，最坏情况下时间复杂度为O(m·n)。n为母串长度，m是模式串长度 56  57 //创建坏字符规则，若坏字符没有出现在模式串中，则直接将模式串移动到坏字符的下一个字符中 58 //若坏字符在模式串中，则把字符串移动到第一个出现坏字符的位置与坏字符重合的位置 59 #define ASIZE 256 60 #define XSIZE 100 61 //坏字符规则 62 void preBmBc(char *x, int m, int bmBc[]) { 63     int i; 64     for (i = 0; i<ASIZE; ++i) 65         bmBc[i] = m; 66     for (i = m-2; i >=0; --i) 67         bmBc[x[i]] = m - i - 1; 68     } 69  70 //好后缀规则，前缀和后缀的最大公共串的长度 71 void suffixes(char* P, int m, int suffix[]){ 72     int i=0,q=0; 73     suffix[m-1]=m; 74     for (i=m-2;i>=0;--i){ 75         q=i; 76         while(q>=0&&P[q]==P[m-1-i+q]) 77             --q; 78         suffix[i]=i-q; 79     } 80 } 81 //计算完好后缀之后，要计算bmGs[i] 表示遇到好后缀时，模式串应该移动的距离， 82 //其中i表示好后缀前面一个字符的位置（也就是坏字符的位置） 83 void preBmGs(char *x, int m, int bmGs[]) { 84     int i, j, suff[XSIZE]; 85     suffixes(x, m, suff); 86     for (i = 0; i < m; ++i) 87         bmGs[i] = m; 88     j = 0; 89     for (i = m - 1; i >= 0; --i) 90         if (suff[i] == i + 1) 91             for (; j < m - 1 - i; ++j)//模式串中没有子串匹配上好后缀，但找到一个最大前缀 92                 if (bmGs[j] == m) 93                     bmGs[j] = m - 1 - i; 94     for (i = 0; i <= m - 2; ++i)//模式串中有子串匹配上好后缀 95         bmGs[m - 1 - suff[i]] = m - 1 - i; 96     } 97  98 void BM_search(char*T,char*P,int m,int bmGs[],int bmBc[]){ 99     int i=0,j = 0;100     while (j <= strlen(T) - strlen(P)) {101         for (i = strlen(P) - 1; i >= 0 && P[i] ==T[i + j]; --i){}102         if (i < 0){103             cout<<j<<endl;//找到匹配104             break;105         } else {106             j += max(bmGs[i], bmBc[T[i]]-(m-1-i));107         }108     }109 }110 111 int main(int argc,char**argv)112 {113     char* s="abcdababda", *p="ababda";114     115     /*int *next=(int*)malloc(p.length()*sizeof(int));116     getNext(p,next);117     int i=kmp_search(s,p,next);118     cout<<i<<endl;*/119 120     int bmBc[ASIZE],bmGs[XSIZE];121     preBmBc(p,strlen(p),bmBc);122     preBmGs(p,strlen(p),bmGs);123     BM_search(s,p,strlen(p),bmGs,bmBc);124 125     return 0;126 }