用c语言写回溯法字符串匹配问题

回溯法也可以用于字符串匹配问题，下面是一个简单的示例程序，使用了C语言实现：

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

#define MAX_N 100

char s[MAX_N];      // 主串
char p[MAX_N];      // 模式串
int flag = 0;       // 是否找到匹配的标志

void backtrack(int i, int j) {
    if (flag) {     // 如果已经找到匹配，直接返回
        return;
    }
    if (j == strlen(p)) {   // 如果模式串已经匹配完了
        flag = 1;   // 找到匹配
        printf("匹配成功，主串中匹配的位置是：%d\n", i - j);
        return;
    }
    if (i == strlen(s)) {   // 如果主串已经匹配完了
        return;
    }
    if (s[i] == p[j]) {     // 如果当前字符匹配成功
        backtrack(i + 1, j + 1);    // 递归下一个字符
    }
    backtrack(i - j + 1, 0);    // 回溯到下一个位置
}

int main() {
    printf("请输入主串和模式串：");
    scanf("%s%s", s, p);
    backtrack(0, 0);    // 从主串的第一个字符开始匹配
    if (!flag) {    // 没有找到匹配
        printf("匹配失败\n");
    }
    return 0;
}

该程序中，backtrack函数用于进行回溯求解，其中i表示主串中当前匹配的位置，j表示模式串中当前匹配的位置，flag表示是否找到匹配的标志。在函数中，首先判断是否已经找到匹配，如果是，直接返回。如果模式串已经匹配完了，说明找到匹配，输出匹配的位置，返回。如果主串已经匹配完了，直接返回。如果当前字符匹配成功，递归下一个字符。如果当前字符匹配失败，回溯到主串中下一个位置，模式串从头开始匹配。在程序中，使用了全局变量，不太优雅，但可以达到简化代码的目的。