最长公共子序列穷举法C语言代码
时间: 2023-08-13 21:39:55 浏览: 56
下面是最长公共子序列穷举法的C语言代码实现:
```c
#include<stdio.h>
#include<string.h>
// 计算两个字符串的最长公共子序列
void LCS(char s1[], char s2[], char maxSeq[]) {
int len1 = strlen(s1);
int len2 = strlen(s2);
int maxLen = 0;
char sub1[100], sub2[100];
// 枚举s1的所有子序列
for(int i = 0; i < len1; i++) {
for(int j = i+1; j <= len1; j++) {
int len = j - i;
strncpy(sub1, s1+i, len);
sub1[len] = '\0';
// 枚举s2的所有子序列
for(int m = 0; m < len2; m++) {
for(int n = m+1; n <= len2; n++) {
len = n - m;
strncpy(sub2, s2+m, len);
sub2[len] = '\0';
// 如果子序列相等,则更新maxLen和maxSeq
if(strcmp(sub1, sub2) == 0 && len > maxLen) {
maxLen = len;
strcpy(maxSeq, sub1);
}
}
}
}
}
}
int main() {
char s1[] = "ABCDGH";
char s2[] = "AEDFHR";
char maxSeq[100];
LCS(s1, s2, maxSeq);
printf("最长公共子序列为:%s\n", maxSeq);
return 0;
}
```
注意,这种方法的时间复杂度为指数级别,对于较长的字符串来说运行时间会很长。因此,这种方法只适用于字符串比较短的情况。在实际应用中,通常会采用更高效的算法来解决最长公共子序列问题。