C语言字符串匹配算法实现 - 使用动态规划

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

bool isMatch(char *pattern, char *text) { int m = strlen(pattern); int n = strlen(text); bool dp[m+1][n+1]; memset(dp, false, sizeof(dp));

dp[0][0] = true;

for (int i = 1; i <= m; i++) {
    if (pattern[i-1] == '*') {
        dp[i][0] = dp[i-1][0];
    }
}

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (pattern[i-1] == '*' || pattern[i-1] == text[j-1]) {
            dp[i][j] = dp[i-1][j-1];
        } else if (pattern[i-1] == '?') {
            dp[i][j] = dp[i-1][j-1];
        } else if (pattern[i-1] == '*') {
            dp[i][j] = dp[i-1][j] || dp[i][j-1];
        } else {
            dp[i][j] = false;
        }
    }
}

return dp[m][n];

}

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

fgets(pattern, sizeof(pattern), stdin);
fgets(text, sizeof(text), stdin);

// 去除换行符
pattern[strcspn(pattern, '\n')] = '\0';
text[strcspn(text, '\n')] = '\0';

if (isMatch(pattern, text)) {
    printf("yes\n");
} else {
    printf("no\n");
}

return 0;

}

/* 说明 / / 该代码使用动态规划的方式判断两个字符串是否匹配。 / / 创建一个二维数组 dp，其中 dp[i][j] 表示 pattern 的前 i 个字符和 text 的前 j 个字符是否匹配。 / / 根据题目的要求，我们可以根据通配符的不同情况来更新 dp 数组。 / / 最后，如果 dp[m][n] 为 true，则表示两个字符串匹配，输出 "yes"，否则输出 "no"。 */

/* 测试说明 / / 你可以尝试使用样例输入进行测试，看看代码是否能够正确判断两个字符串是否匹配。 / / 你还可以尝试其他的测试用例，包括包含多个通配符的情况、字符串中包含空格的情况等，以确保代码的正确性。 */