[原创]内存特征码搜索_字符串匹配算法_Boyer-Moore思想的实现_CPP源码分享-编程技术-看雪-安全社区|安全招聘|kanxue.com

[原创]内存特征码搜索_字符串匹配算法_Boyer-Moore思想的实现_CPP源码分享

发表于: 2021-9-12 11:26 9142

[原创]内存特征码搜索_字符串匹配算法_Boyer-Moore思想的实现_CPP源码分享

黄裕顺

2021-9-12 11:26

9142

早些年就玩过内存特征码搜索,
学习过Sunday,必须他理解最简单
然后写了个X86 X64通用特征码匹配
发帖这边
https://www.chinapyg.com/thread-98948-1-1.html
然后又把kmp学了一下,分享这边
https://www.chinapyg.com/thread-135745-1-1.html
现在闲着把BM的思想也理解了一下,
参考了一些先人的写法逻辑,终于感觉能写出来了
把搜索的那几种算法都玩一次,

暴力就不说了
kmp:我的理解就是最简单的匹配失败后,尝试不断向后推进,记录这个尝试结果,用于后续
sunday : 利用hash表开放式寻址,直接定位char的定长256,记录子串字符出现最后一个位置来推进
Boyer-Moore :这个大多数文章都只有思路,坏字符应该就说的Sunday方式,而好字符应该就是kmp这类思路,从子串推进,然后结合2者

我就把这2者结合来写了,
主要推进Sunday也就是坏字符的思路,
加入kmp之类的好字符思路兜底,
因为只是兜底所以没有去跟坏字符比长度取最大来推进,
毕竟对比再去最大,这花销,好多时候达到的推进估计补不回来,
所以我就直接推进kmp改进后的表了,不去对比取最大,节约点开销

听说玩这些的估计不会有易语言玩家,
所以我特别改了个英文版来发
源码如下:

intptr_t BM_find(const char* t, size_t lt, const char* s, size_t ls)
{

    //建立跳转表

    size_t* Tpkmp = new size_t[ls];

    intptr_t k = 0, coiled = 1;

    //计算子串特征_[next表]

    for (size_t i = 1; i < ls; i++)

    {

        if (s[i] == s[k]) { ++k; }

        else { k = (s[i] == s[0]) ? 1 : 0; }

        Tpkmp[i - 1] = i - k;

    }

    //优化表

    k = -1;

    for (size_t i = 0; i < ls - 1; i++)

    {

        if (s[i] == s[ls - 1]) { k = i; }

        if (s[i] == s[i + 1] && coiled)

        {

            Tpkmp[i + 1] = Tpkmp[i] > ++coiled ? Tpkmp[i] : coiled;

        }

        else

        {

            coiled = 0;

        }
 
    }

    Tpkmp[0] = ls - k - 1;

    for (size_t i = 1; i < ls; i++)

    {

        if (Tpkmp[ls - i] < Tpkmp[0]) { Tpkmp[ls - i] = Tpkmp[0]; }

    }

    //开始制作哈希表

    char Thash[256];

    for (size_t i = 0; i < 256; i++) { Thash[i] = ls; }

    for (size_t i = 0; i < ls; i++) { Thash[(size_t)s[i] & 0xff] = ls - 1 - i; }

    //制表到此完成

    ls -= 1;

    lt -= ls;

    intptr_t out = -1;

    //开始遍历搜索

    for (size_t i = 0; i < lt;)

    {

        //坏字符

        if (Thash[(size_t) * (t + i + ls) & 0xff]) { i += Thash[(size_t) * (t + i + ls) & 0xff]; goto fail; }

        //好字符

        for (size_t n = 0; n < ls; n++)

        {

            if (*(t + i + n) != *(s + n)) { i += Tpkmp[n]; goto fail; }

        }

        //找到_结束循环

        out = i; break;

    fail:;

    }

    //收尾工作

    delete[] Tpkmp;

    return out;
}

intptr_t BM_find(const char* t, size_t lt, const char* s, size_t ls)

{

//建立跳转表

size_t* Tpkmp = new size_t[ls];

intptr_t k = 0, coiled = 1;

//计算子串特征_[next表]

for (size_t i = 1; i < ls; i++)

{

if (s[i] == s[k]) { ++k; }

else { k = (s[i] == s[0]) ? 1 : 0; }

Tpkmp[i - 1] = i - k;

}

//优化表

k = -1;

for (size_t i = 0; i < ls - 1; i++)

{

if (s[i] == s[ls - 1]) { k = i; }

if (s[i] == s[i + 1] && coiled)

{

Tpkmp[i + 1] = Tpkmp[i] > ++coiled ? Tpkmp[i] : coiled;

}

else

{

coiled = 0;

}

登录后可查看完整内容

[招生]科锐逆向工程师培训(2025年3月11日实地，远程教学同时开班, 第52期)！

#开源分享

收藏・17

免费・8

支持

赞赏记录

参与人

雪币

留言

时间

心游尘世外

感谢你的贡献，论坛因你而更加精彩！

2024-9-5 01:41

QinBeast

看雪因你而更加精彩！

2024-9-4 01:53

Roje

为你点赞~

2023-1-12 23:41

PLEBFE

为你点赞~

2022-7-30 06:43

mb_yajtrjte

为你点赞~

2021-9-20 20:42

superlover

为你点赞~

2021-9-19 13:43

DemonsEllen

为你点赞~

2021-9-13 13:30

ericyudatou

为你点赞~

2021-9-12 14:03

最新回复 (8)

院士

雪币： 4328

活跃值： (4681)

能力值：

( LV2，RANK：10 )

在线值：

发帖

回帖

188

粉丝

关注

私信

院士: 2 楼

顶顺表哥，话说表哥好久没冒泡了，能说下需要那几个参数不？

2021-9-12 11:41

黄裕顺

雪币： 243

活跃值： (813)

能力值：

( LV2，RANK：10 )

在线值：

发帖

回帖

粉丝

关注

私信

黄裕顺: 3 楼

院士顶顺表哥，话说表哥好久没冒泡了，能说下需要那几个参数不？[em_13]

主串,主串长度,子串,子串长度四个参数

2021-9-12 12:37

Mxixihaha

雪币： 4981

活跃值： (4928)

能力值：

( LV2，RANK：10 )

在线值：

发帖

回帖

598

粉丝

关注

私信

Mxixihaha: 4 楼

void get_next(unsigned char* t , int tl, int* next) //获取回溯的表
{
 
    int len = tl;
    int i = 0;
    int j = -1;  //尾缀
    next[0] = -1; //前缀
    while (i < len)
    {
        if (j == -1 || t[i] == t[j])
        {
            j++;
            i++;
 
            //与普通KMP差异的地方
            if (t[i] != t[j])
            {
                next[i] = j;
            }
            else
            {
                next[i] = next[j];
                //这个主要是考虑匹配失败的时候，如果匹配失败了，必然往回回溯，但是如果回溯的下一个
                //地方还是这个元素，必然没有意义，还要往前回溯，那就把前一个元素的回溯值直接交给后面就可以了
 
                //比如  S = abacababc
                //      T = abab
                //匹配第四个元素不同，必然往前回溯，变成
                //      S = abacababc
                //        T = abab
                //对着的还是b，不可能匹配成功的。
                //所以，如果有匹配的子串，而且其下一个元素也相同，那就意味着，如果下一个元素匹配失败的时候
                //往前回溯，对应元素还是这个值。
            }
            //差异结束
 
        }
        else
        {
            j = next[j]; 
        }
    }
}
 
int Index_KMP(unsigned char* S , int SLength, unsigned char* T , int TLength)
{
    int next[260]={0};
    get_next(T,TLength, next);//获取模式串用于标识回溯位置的表
    int i = 0;
    int j = 0;
    int Slen = SLength;//主串
    int Tlen = TLength; //模式串
 
    while (i < Slen && j < Tlen)
    {
        if (j == -1 || S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j == Tlen)//匹配成功
    {
        return i - j;
    }
    else
    {
        return -1;
    }
 
}