字符串模式匹配的几种算法

1、KMP算法

KMP算法程序看起来比较简单，但是求next数组的过程还是比较难理解，next数组实质就是求最大的前后缀，该算法的复杂度是O(m+n)，算法流程如下：

  • 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
    • 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
    • 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。

详细的讲解看以看一下这篇文章 http://blog.csdn.net/v_july_v/article/details/7041827

求next数组的代码：

//优化过后的next 数组求法  
void GetNextval(char* p, int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀    
        if (k == -1 || p[j] == p[k])  
        {  
            ++j;  
            ++k;  
            //这里主要是为了防止二次匹配失败 
            if (p[j] != p[k])  
                next[j] = k;   
            else  
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]  
                next[j] = next[k];  
        }  
        else  
        {  
            k = next[k];  
        }  
    }

KMP代码和求next数组的代码十分的相似：

int KmpSearch(char* s, char* p)  
{  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen)  
    {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

2、BM算法

BM算法是从后向前开始比较，这个算法主要用到了两个预处理数组坏符号异动表和好后缀移动表，在每次匹配失败时，从这两个表中选择最大的一个值最为下次匹配的开始位置，详细的介绍可以参考这篇文章 http://blog.csdn.net/eric491179912/article/details/6210009

代码：

void preBmBc(char *x, int m, int bmBc[]) {  
  
   int i;  
  
   for (i = 0; i < ASIZE; ++i)  
  
      bmBc[i] = m;  
  
   for (i = 0; i < m - 1; ++i)  
  
      bmBc[x[i]] = m - i - 1;  
  
}  
  
void suffixes(char *x, int m, int *suff) {  
  
   int f, g, i;  
  
  f = 0；  
  
   suff[m - 1] = m;  
  
   g = m - 1;  
  
   for (i = m - 2; i >= 0; --i) {  
  
      if (i > g && suff[i + m - 1 - f] < i - g)  
  
         suff[i] = suff[i + m - 1 - f];  
  
      else {  
  
         if (i < g)  
  
            g = i;  
  
         f = i;  
  
         while (g >= 0 && x[g] == x[g + m - 1 - f])  
  
            --g;  
  
         suff[i] = f - g;  
  
      }  
  
   }  
  
}  
  
void preBmGs(char *x, int m, int bmGs[]) {  
  
   int i, j, suff[XSIZE];  
  
   suffixes(x, m, suff);  
  
   for (i = 0; i < m; ++i)  
  
      bmGs[i] = m;  
  
   j = 0;  
  
   for (i = m - 1; i >= 0; --i)  
  
      if (suff[i] == i + 1)  
  
         for (; j < m - 1 - i; ++j)  
  
            if (bmGs[j] == m)  
  
               bmGs[j] = m - 1 - i;  
  
   for (i = 0; i <= m - 2; ++i)  
  
      bmGs[m - 1 - suff[i]] = m - 1 - i;  
  
}  
  
void BM(char *x, int m, char *y, int n) {  
  
   int i, j, bmGs[XSIZE], bmBc[ASIZE];  
  
   /* Preprocessing */  
  
   preBmGs(x, m, bmGs);  
  
   preBmBc(x, m, bmBc);  
  
   /* Searching */  
  
   j = 0;  
  
   while (j <= n - m) {  
  
      for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);  
  
      if (i < 0) {  
  
         OUTPUT(j);  
  
         j += bmGs[0];  
  
      }  
  
      else  
  
         j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);  
  
   }  
  
}

3、Horspool算法
Horspool是BM算法的简化版本，该算法不仅简单，而且在处理随机串的时候，效率不一定比BM算法低。该算法的最差效率是O(mn)，但对于随机文本来说，它的效率属于O(n)，算法主要流程：

(1) 构造转移表

      t(c) = 模式的长度m(如果c不包含在m-1个字符中)

            = 模式从右到左第一个出现c的距离(其他情况)

(2) 将模式和文本的开始出对齐

(3) 重复下面的过程，知道发现一个匹配子串或者模式到达了文本的最后一个字符以外。从模式的最后一个字符开始，比较模式和文本中的相应字符，知道：要么所有m个字符都匹配，要么遇到了一个不匹配的字符。

     在后一种情况下，如果c是当前文本中和模式的最后一个字符相对齐的字符，则将模式沿着文本向右移动t(c)个字符。

代码：

void ShitTable(char *P,int Plen,int *Table，int Table_Size)
{
    for(int i=0;i<Table_Size;i++) //将转移表初始化为Plen
        Table[i]=Plen;
    for(int i=0;i<Plen-2;i++)
        Table[P[i]]=Plen-1-i;
}

int HorspoolMatching(char*P,int Plen,char*T,int Tlen,int *Table)
{
    ShitTable(P,Plen,Table);
    int i=Plen-1;//模式最右端位置
    while(i<=Tlen-1)
    {
        int k=0; //匹配字符的个数
        while(k<=Plen-1 && P[Plen-1-k] == T[i-k])
            k++;
        if(k==Plen)
            return i-Plen+1;
        else 
            i=i+Table[T[i]];
    }
    return -1;
}

4、sunday算法

Sunday算法的思想和BM算法中的坏字符思想非常类似。

差别只是在于Sunday算法在失配之后，是取目标串中当前和模式串对应的部分后面一个位置的字符来做坏字符匹配。
如下图：
下标数：01234567890
目标串：abcdefghijk
模式串：bxcd
 
BM算法在b和x失配后，坏字符为b(下标1)，在模式串中寻找b的位置，找到之后就对应上，移到下面位置继续匹配。
目标串：abcdefghijk
模式串： bxcd
 
而在sunday算法中，对于上面的匹配，发现失配后，是取目标串中和模式串对应部分后面的一个字符，也就是e，然后用e来做坏字符匹配。
e在模式串中没有，所以使用sunday算法，接下来会移动到下面的位置继续匹配。
目标串：abcdefghijk
模式串：        bxcd
 
从这里可以看出，Sunday算法比BM算法的位移更大，所以Sunday算法比BM算法的效率更高。但是最坏的时间复杂度仍然有o(目标串长度*模式串长度)。考虑这样的目标串：baaaabaaaabaaaabaaaa，要在里面搜索aaaaa，显然是没有匹配位置。但是如果用Sunday算法，坏字符大部分都是a，而模式串中又全部都是a，所以在大部分情况下，发现失配后模式串只能往右移动1位。而如果用改进的KMP算法，仍然是可以保证线性时间内匹配完。
 
另外，使用Sunday算法不需要固定地从左到右匹配或者从右到左的匹配(这是因为失配之后我们用的是目标串中后一个没有匹配过的字符)，我们可以对模式串中的字符出现的概率事先进行统计，每次都使用概率最小的字符所在的位置来进行比较，这样失配的概率会比较大，所以可以减少比较次数，加快匹配速度。
如下面的例子：
目标串：abcdefghijk
模式串：aabcc
模式串中b只出现了一次，a,c都出现了2次，所以我们可以先比较b所在的位置（只看模式串中的字符的话，b失配的概率会比较大）。
 
核心代码：
bool BadChar(const char *pattern, int nLen, int *pArray, int nArrayLen)  
{  
    if (nArrayLen < 256)  
    {  
        return false;  
    }  
    for (int i = 0; i < 256; i++)  
    {  
        pArray[i] = -1;  
    }  
    for (int i = 0; i < nLen; i++)  
    {  
        pArray[pattern[i]] = i;  
    }  
    return true;  
}  
  
int SundaySearch(const char *dest, int nDLen,  
                 const char *pattern, int nPLen,  
                 int *pArray)  
{  
    if (0 == nPLen)  
    {  
        return -1;  
    }  
    for (int nBegin = 0; nBegin <= nDLen-nPLen; )  
    {  
        int i = nBegin, j = 0;   
        for ( ;j < nPLen && i < nDLen && dest[i] == pattern[j];i++, j++);  
        if (j == nPLen)  
        {  
            return nBegin;  
        }  
        if (nBegin + nPLen > nDLen)  
        {  
            return -1;  
        }  
        else  
        {  
            nBegin += nPLen - pArray[dest[nBegin+nPLen]];  
        }  
    }  
    return -1;  
}
 
总之，Sunday算法简单易懂，思维跳出常规匹配的想法，从概率上来说，其效率在匹配随机的字符串时比其他匹配算法还要更快。
 
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jianxingzhe/p/4039096.html