字符串匹配问题回溯法c语言代码
时间: 2023-07-30 07:07:16 浏览: 51
下面是一个简单的使用回溯法解决字符串匹配问题的C语言代码:
```
#include <stdio.h>
#include <string.h>
int match(char *str, char *pattern) {
int i = 0, j = 0;
int len1 = strlen(str);
int len2 = strlen(pattern);
while (i < len1 && j < len2) {
if (str[i] == pattern[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == len2) {
return i - j;
} else {
return -1;
}
}
int main() {
char str[] = "hello, world!";
char pattern[] = "world";
int pos = match(str, pattern);
if (pos >= 0) {
printf("Matched at position %d\n", pos);
} else {
printf("Not matched\n");
}
return 0;
}
```
这个代码中,使用了两个指针 i 和 j 分别指向长字符串和短字符串的当前位置,依次比较它们指向的字符,如果相等,则继续比较下一个字符,否则回溯到上一个位置重新匹配。如果短字符串所有字符都匹配成功,则返回匹配位置,否则返回 -1。