C语言实现字符串匹配算法 - 包含通配符 * 和 ? 的匹配

C语言实现字符串匹配算法 - 包含通配符 * 和 ? 的匹配

本文介绍了使用 C 语言实现的字符串匹配算法，该算法可以处理包含通配符 * 和 ? 的字符串，其中 * 代表 0 个或多个字符，? 代表 1 个字符。代码示例清晰易懂，并附有详细的解释，帮助您理解算法原理和实现细节。

问题描述

判断两个字符串是否匹配，其中一个字符串中包括通配符''或'?'（串），另一个为不包含''和'?'的确定字符串。

输入形式

分两行输入两个字符串，以#结束，其中一个字符串中包括通配符''或'?'（串），另一个为不包含''和'?'的确定字符串。

输出形式

判断两个字符串是否匹配，若匹配，输出yes，不匹配输出no

样例输入

da?a*tu*e#
datastructure#

样例输出

yes

C语言代码实现

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

bool isMatch(char *str, char *pattern) {
    // 边界情况处理
    if (*pattern == '\0') {
        return *str == '\0';
    }
    
    // 处理通配符"*"的情况
    if (*pattern == '*') {
        // 跳过连续的"*"字符
        while (*pattern == '*') {
            pattern++;
        }
        
        // 遍历字符串str，尝试匹配剩余部分
        while (*str != '\0') {
            if (isMatch(str, pattern)) {
                return true;
            }
            str++;
        }
        
        return isMatch(str, pattern);
    }
    
    // 处理通配符"?"的情况
    if (*str != '\0' && (*str == *pattern || *pattern == '?')) {
        return isMatch(str + 1, pattern + 1);
    }
    
    return false;
}

int main() {
    char str[100];
    char pattern[100];

    // 从标准输入读取字符串
    scanf("%[^#]#", str);
    scanf("%s", pattern);
    
    // 调用isMatch函数判断两个字符串是否匹配
    if (isMatch(str, pattern)) {
        printf("yes\n");
    } else {
        printf("no\n");
    }
    
    return 0;
}

代码解释

这段代码通过递归的方式判断两个字符串是否匹配。其中，isMatch函数用于比较字符串str和pattern是否匹配。在函数中，我们处理了通配符"*"和"?"的情况，并通过递归调用isMatch函数来处理其中的子问题。最后，根据isMatch函数的返回值输出结果。

• **isMatch(char str, char pattern) 函数用于比较两个字符串是否匹配，其中 str 是目标字符串，pattern 是包含通配符的模式字符串。
• 边界情况处理：当模式字符串 pattern 为空时，目标字符串 str 也必须为空才匹配，因此返回 *str == '\0'。
• 处理通配符 "*" 的情况：当模式字符串 pattern 的当前字符为 "*" 时，我们需要遍历目标字符串 str，尝试匹配剩余部分。
• 处理通配符 "?" 的情况：当模式字符串 pattern 的当前字符为 "?" 或与目标字符串 str 的当前字符相同时，则继续比较下一个字符。
• 递归调用：函数 isMatch 通过递归调用自身，处理模式字符串中通配符的匹配。

总结

本文介绍了使用 C 语言实现的字符串匹配算法，该算法可以处理包含通配符 * 和 ? 的字符串，代码示例清晰易懂，并附有详细的解释，希望对您有所帮助。