穷举法最长公共子序列c++
时间: 2023-12-18 11:29:07 浏览: 37
以下是使用穷举法求解最长公共子序列的C++代码:
```c++
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int f[N][N];
int main()
{
string s1, s2;
cin >> s1 >> s2;
int n = s1.size(), m = s2.size();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = max(f[i-1][j], f[i][j-1]);
if(s1[i-1] == s2[j-1])
f[i][j] = max(f[i][j], f[i-1][j-1]+1);
}
cout << f[n][m] << endl;
return 0;
}
```
相关问题
穷举法求最长公共子序列
穷举法是一种简单直观的求解问题的方法,它通过枚举所有可能的情况来找到最优解。在求解最长公共子序列(Longest Common Subsequence,简称LCS)的问题中,穷举法可以用来找到所有可能的子序列,并从中选取最长的一个作为结果。
穷举法求解最长公共子序列的步骤如下:
1. 首先,我们需要找到两个字符串的所有子序列。一个字符串的子序列是指从该字符串中删除0个或多个字符后得到的新字符串。
2. 然后,我们对两个字符串的所有子序列进行比较,找到它们之间相同的部分。
3. 最后,我们选择最长的相同部分作为最长公共子序列。
以下是穷举法求解最长公共子序列的示例代码:
```python
def find_lcs(str1, str2):
m = len(str1)
n = len(str2)
lcs = ""
max_length = 0
for i in range(2**m):
subsequence = ""
for j in range(m):
if (i >> j) & 1:
subsequence += str1[j]
if len(subsequence) > max_length and is_subsequence(subsequence, str2):
lcs = subsequence
max_length = len(subsequence)
return lcs
def is_subsequence(subsequence, string):
i = 0
j = 0
while i < len(subsequence) and j < len(string):
if subsequence[i] == string[j]:
i += 1
j += 1
return i == len(subsequence)
# 示例调用
str1 = "ABCD"
str2 = "ACDF"
lcs = find_lcs(str1, str2)
print("最长公共子序列为:", lcs)
```
穷举法实现最长公共子序列
以下是使用穷举法实现最长公共子序列的Python代码:
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
result = ""
for i in range(2 ** m):
subsequence = ""
for j in range(m):
if i & (2 ** j):
subsequence += X[j]
if subsequence in Y and len(subsequence) > len(result):
result = subsequence
return result
```
该函数接受两个字符串X和Y作为输入,并返回它们的最长公共子序列。该函数使用了穷举法,通过枚举X的所有子序列,并检查它们是否也是Y的子序列,从而确定它们是否为X和Y的公共子序列。在检查中记录最长公共子序列,最后返回结果。