动态规划法解决字符串匹配问题c语言

字符串匹配问题可以使用动态规划法进行解决。具体来说，可以使用一个二维数组dp[i][j]表示文本串中前i个字符与模式串中前j个字符是否匹配。其中，dp[0][0]表示两个空串匹配，dp[i][0]表示空模式串与任何文本串都匹配，dp[0][j]则表示文本串为空，只有当模式串中前j个字符均为*时才为匹配。

状态转移方程如下：

1. 当模式串第j个字符是*时：

dp[i][j] = dp[i][j-1] || dp[i-1][j]

解释：*可以表示空字符或者匹配一个或多个字符。dp[i][j-1]表示*匹配0个字符，dp[i-1][j]表示*匹配一个或多个字符。

2. 当模式串第j个字符不是*时：

dp[i][j] = dp[i-1][j-1] && (text[i] == pattern[j] || pattern[j] == '?')

解释：当模式串第j个字符不是*时，只有当文本串中第i个字符与模式串中第j个字符相同或者模式串中第j个字符为?时才能匹配。

最终的匹配结果为dp[text_len][pattern_len]，其中text_len和pattern_len分别为文本串和模式串的长度。

以下是使用C语言实现字符串匹配问题的动态规划法的示例代码：

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

#define MAX_LEN 1000

int dp[MAX_LEN][MAX_LEN];

int isMatch(char* text, char* pattern) {
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);
    
    // 初始化dp数组
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    // 处理dp数组的第一行
    for (int j = 1; j <= pattern_len; j++) {
        if (pattern[j-1] == '*') {
            dp[0][j] = dp[0][j-1];
        }
    }

    // 处理dp数组的其余部分
    for (int i = 1; i <= text_len; i++) {
        for (int j = 1; j <= pattern_len; j++) {
            if (pattern[j-1] == '*') {
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j-1] && (text[i-1] == pattern[j-1] || pattern[j-1] == '?');
            }
        }
    }

    // 返回匹配结果
    return dp[text_len][pattern_len];
}

int main() {
    char text[MAX_LEN], pattern[MAX_LEN];
    printf("请输入文本串：");
    scanf("%s", text);
    printf("请输入模式串：");
    scanf("%s", pattern);
    if (isMatch(text, pattern)) {
        printf("匹配成功！\n");
    } else {
        printf("匹配失败！\n");
    }
    return 0;
}