c语言实现的带通配符匹配算法

带通配符匹配算法

带通配符匹配算法是一种字符串匹配算法，可以匹配包含通配符的字符串。通配符可以代表任何字符或者一组字符。例如，字符串“a*b”可以匹配“ab”、“acb”、“adfb”等字符串。本文将详细介绍如何使用C语言实现带通配符匹配算法。

实现步骤

1. 我们首先需要确定通配符的类型。一般情况下，通配符分为两种类型：“” 和 “?” 。其中，“” 可以匹配任意数量、任意类型的字符，“?” 可以匹配任意一个字符。

2. 接着，我们需要遍历匹配字符串和模式串，逐个比较字符。当遇到通配符时，我们需要特殊处理。具体操作如下：

3. 如果遇到了 “*” ，我们记录下此时匹配字符串和模式串的指针位置，并继续遍历模式串，同时记录答案。

4. 如果遇到了 “？” ，则该位置可以匹配任意一个字符，直接跳过即可。

5. 如果当前字符相同，或者模式串中遇到了 “?” ，则继续遍历下一个字符。如果匹配失败，则回溯到最近一次 “*” 的位置，并重复上述操作。

6. 最后，如果匹配成功，则返回匹配字符串的起始位置，以及模式串中记录的偏移量。

代码实现如下：

#include <stdio.h>
#include <string.h>

int match(char const* s, char const* p)
{
    char const* star = NULL;
    char const* ss = s;

    while (*s)
    {
        if (*p == '?' || *p == *s)
        {
            ++p;
            ++s;
            continue;
        }
        if (*p == '*')
        {
            star = p++;
            ss = s;
            continue;
        }

        if (star)
        {
            p = star + 1;
            s = ++ss;
            continue;
        }

        return 0;
    }

    while (*p == '*')
    {
        ++p;
    }

    return !*p;
}

int main()
{
    char const* s = "hello world";
    char const* p = "?e*?ld";
    int res = match(s, p);
    if (res)
    {
        printf("Match success at position %d, pattern offset %d.\n", res - s, res - p);
    }
    else
    {
        printf("Match failed.\n");
    }
    return 0;
}

示例说明

示例一

匹配 “hello world” 和 “?e*?ld”

• 匹配 “h” 和 “?” ：匹配成功
• 匹配 “e” 和 “e” ：匹配成功
• 匹配 “l” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “l” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “o” 和 “?” ：匹配成功
• 匹配 “w” 和 “w” ：匹配成功
• 匹配 “o” 和 “o” ：匹配成功
• 匹配 “r” 和 “r” ：匹配成功
• 匹配 “l” 和 “l” ：匹配成功
• 匹配 “d” 和 “d” ：匹配成功

匹配成功，起始位置为0，偏移量为0。

示例二

匹配 “picture.wav” 和 “*wav”

• 匹配 “p” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “p” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “p” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “p” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “i” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “c” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “t” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “u” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “r” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “e” 和 “*” ：记录下匹配位置，匹配失败
• 匹配 “.” 和 “*” ：记录下匹配位置，匹配成功
• 匹配 “w” 和 “w” ：匹配成功
• 匹配 “a” 和 “a” ：匹配成功
• 匹配 “v” 和 “v” ：匹配成功

匹配成功，起始位置为0，偏移量为0。