Study Notes
0%

模式匹配Brute-Force算法(1)

发表于 更新于 分类于

简介

Brute-Force算法又称暴力匹配算法、朴素匹配算法。
基本原理就是：从文本串的每个字符开始依次与模式串进行匹配。
设文本串长度为n，模式串长度为m，时间复杂度就是O(n*m)。

示例代码

如下为匹配单字节字符示例，而匹配宽字符时，仅函数声明不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char* BruteForceSearchA(char* txt, int tn, char* pat, short pn)
//wchar_t* BruteForceSearchW(wchar_t* txt, int tn, wchar_t* pat, short pn)
{
    if (!txt || !pat || (pn <= 0) || (pn > tn)) return 0;
    for (int i = 0; i <= (tn - pn); i++)
    {
        short j;
        for (j = 0; j < pn; j++)
        {
            if (pat[j] != txt[i + j]) break;
        }
        if (j == pn) return (txt + i);
    }
    return 0;
}

搜索字节码示例（带通配符0xCC）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
unsigned char* PatternSearchByte(unsigned char* dat, int dn, unsigned char* pat, short pn)
{
    if (!dat || !pat || (pn <= 0) || (pn > dn)) return 0;
    __try
    {
        for (int i = 0; i <= (dn - pn); i++)
        {
            short j;
            for (j = 0; j < pn; j++)
            {
                if ((pat[j] != dat[i + j]) && (pat[j] != 0xCC)) break;
            }
            if (j == pn) return (dat + i);
        }
    }
    __except (1) // EXCEPTION_EXECUTE_HANDLER
    {
    }
    return 0;
}