字符串匹配算法

算法

---

1.KMP算法

http://kb.cnblogs.com/page/176818/

2.BM（Boyer-Moore）算法

http://kb.cnblogs.com/page/176945/

3.sunday算法

#include <stdio.h>
#include "Sunday.h"
int main()
{
    char* text = "blog.csdn,blog.net";
    char* pattern = "csdn,blog"    ;
    Sunday sunday;
    printf("The First Occurence at: %d/n",sunday.find(pattern,text));
    return 1;
}

/* Sunday.h */
class Sunday 
{
public:
   Sunday();
   ~Sunday();
public:
    int find(const char* pattern, const char* text);
private:
    void preCompute(const char* pattern);
private:
    //Let's assume all characters are all ASCII
    static const int ASSIZE = 128;
    int _td[ASSIZE] ;
    int _patLength;
    int _textLength;
};

/* Sunday.cpp */
Sunday::Sunday()
{
}
Sunday::~Sunday()
{
}
void Sunday::preCompute(const char* pattern)
{
    for(int i = 0; i < ASSIZE; i++ ) 
        _td[i] = _patLength + 1;
    const char* p;
    for ( p = pattern; *p; p++)
        _td[*p] = _patLength - (p - pattern);
}
int Sunday::find(const char* pattern, const char* text)
{
    _patLength = strlen( pattern );
    _textLength = strlen( text );
    if ( _patLength <= 0 || _textLength <= 0)
        return -1;
    preCompute( pattern );
    const char *t, *p, *tx = text;
    while (tx + _patLength <= text + _textLength) 
    {
        for (p = pattern, t = tx; *p; ++p, ++t)
        {
            if (*p != *t)
                break;
        }
        if (*p == 0)
            return tx-text;
        tx += _td[tx[_patLength]]; 
    }
    return -1;
}

4.shift and/shift or算法

http://www.cnblogs.com/longdouhzt/archive/2011/09/25/2190550.html
Shift-And算法思想较之KMP算法很简单，设模式字符串为P，它主要通过保存一个集合D（D中记录了P中所有与当前已读text的某个后缀相匹配的前缀），每当text有新的字符读入，算法利用位并行机制来更新这个集合D。设P长度为m，则集合D可表示为D = dm…d1 而用D[j]代表dj，D[j]=1当且仅当p1…pj 是 t1…ti 的某个后缀，当D[m]=1时，就认为P已经于text匹配。
当读入下一个字符 ti+1, 需要计算新的集合 D′. 当且仅当D[j]=1并且 ti+1 等于 pj+1时D'[j+1]=1. 这是因为D[j]=1时有 p1…pj 是 t1…ti 的一个后缀，而当ti+1 等于 pj+1可推出p1…pj +1是 t1…ti+1 的一个后缀.这个集合可通过位运算来更新.
算法首先建立一个数组B, 数组长度为text串所属字符集长度（例如A-Z的话数组B的长度为26.） 如果P的第j为等于c则将B[c] 中第j位置为1.
因为要预处理计算B，如果字符集很大的话，并不划算。如果m很长的话（大于机器字长），也很不方便。所以这种算法适用于字符集较小，模式串小于机器字长的情况。当然对于模式串较长的情况，也是比brute force要快的，只是逻辑上要复杂些。
Shift-And的代码如下，这里假设字符集的大小为128

int shift_and(char * s, int len_s, char * p, int len_p)
{
     int B[128];
     memset(B, 0, sizeof(B));
     int i;
     for (i=0; i<len_p; i++)
        B[p[i]] |= 1<<i;
     int D = 0;
     for (i=0; i<len_s; i++)
     {
        D = ((D<<1) | 1) & B[s[i]];  //D<<1与1位或操作，是可以让匹配随时从当前字符开始，使用位运算实现了并行
        if (D & (1<<(len_p-1)))
         return i - len_p+1;
     }
     return -1;
}

5.Brute Force(蛮力算法）

strstr的实现。需要说明的是strstr是c语言提供的使用Brute Force实现的字符串匹配，简单、通用是其最大的优点。时间复杂度是O(mn)。

// 下面是Microsoft的实现
//经典算法
//比KMP算法简单,没有KMP算法高效
char * __cdecl strstr (
        const char * str1,
        const char * str2
        )
{
        char *cp = (char *) str1;
        char *s1, *s2;
        if ( !*str2 )
            return((char *)str1);
        while (*cp)
        {
                s1 = cp;
                s2 = (char *) str2;
                while ( *s1 && *s2 && !(*s1-*s2) )
                        s1++, s2++;
                if (!*s2)
                        return(cp);
                cp++;
        }
        return(NULL);
}

6.RK算法

某一天在图书馆的一本算法分析设计书上翻到的。思路很新颖！和大家分享下。
在串匹配的简单算法中，把文本每m个字符构成的字符段作为一个字段，和模式进行匹配检查。如果能对一个长度为m的字符
串赋以一个Hash函数。那么显然只有那些与模式具有相同hash函数值的文本中的字符串才有可能与模式匹配，这是必要条件，而没有必要去考虑文本中所有长度为m的字段，因而大大提高了串匹配的速度。因此RK算法的思想和KMP，BM，Sunday等思路迥然不同！
（事实上，之前的串匹配方法，是将模式串的一个一个字符作为小的特征去分别进行匹配，而RK算法则是将串整体作为一个特征！难就难在单个字符的特征很容易想得到，整体作为一个特征就没那么容易想得到了）
如果把整体作为一个特征，那么如何快速的求出这个整体特征的特征值？？
模式串的特征值仅需求一次即可。对于文本中的任意m个字符构成的字串如何快速的求特征就是个难点了。
抛砖引玉，这里给出一个简单的特征计算。将字符串的每一个字符看做一个数，那么这个字符串的就是一个数字数组，通过积分向量可以快速任意一个长度子字符串的向量和。可以把字符串的对应的字符数组的元素和看做这个字符串整体特征。这个特征是可以再O（1）的时间内求出的。其实原始的RK算法里面是把字符串看做一个26进制数在计算特征的。这里就不啰嗦了，有兴趣的可以深入查找
aabsee sds 模式串 ees
ees
发现 see向量和 == ees的向量和
然后就对see和ees做逐个字符的比较。发现不匹配继续往下走
aabsees ds 模式串 ees
ees
发现 ees向量和 == ees的向量和
然后就对ees和ees做逐个字符的比较。发现匹配OK。