c实现动态规划最长公共子串
时间: 2023-11-22 12:49:57 浏览: 62
以下是C语言实现动态规划求解最长公共子串的代码:
```c
#include <stdio.h>
#include <string.h>
#define MAXLEN 100
int max(int a, int b) {
return a > b ? a : b;
}
int lcs(char *str1, char *str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int dp[MAXLEN][MAXLEN] = {0}; // 初始化为0
int maxLen = 0; // 最长公共子串长度
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = max(maxLen, dp[i][j]);
}
}
}
return maxLen;
}
int main() {
char str1[MAXLEN], str2[MAXLEN];
printf("请输入两个字符串:\n");
scanf("%s%s", str1, str2);
int len = lcs(str1, str2);
printf("最长公共子串长度为:%d\n", len);
return 0;
}
```