代码实现最长子序列暴力算法
时间: 2023-05-10 15:55:28 浏览: 60
最长子序列暴力算法的代码实现如下:
```
#include <iostream>
#include <cstring>
using namespace std;
int main() {
string s1, s2;
cin >> s1 >> s2;
int len1 = s1.length(), len2 = s2.length();
int ans = 0;
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
int k = 0;
while (i + k < len1 && j + k < len2 && s1[i + k] == s2[j + k]) {
k++;
}
ans = max(ans, k);
}
}
cout << ans << endl;
return 0;
}
```
该算法的时间复杂度为 $O(n^3)$,不适用于较长的字符串。
相关问题
最长子序列python
最长子序列(Longest Subsequence)是指在一个序列中找到最长的子序列,该子序列在原序列中的元素顺序保持不变,但可以不连续。在Python中,可以使用动态规划算法来解决最长子序列问题。
以下是一个使用动态规划算法求解最长递增子序列(Longest Increasing Subsequence,简称LIS)的示例代码:
```python
def longest_increasing_subsequence(nums):
n = len(nums)
dp = * n # 初始化dp数组,dp[i]表示以nums[i]结尾的最长递增子序列长度
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 示例输入
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# 调用函数求解最长递增子序列长度
result = longest_increasing_subsequence(nums)
print("最长递增子序列长度为:", result)
```
输出结果为:
```
最长递增子序列长度为: 4
```
python 最长子序列
Python最长子序列问题是指在两个序列中找到一个共同的子序列,该子序列在两个序列中的相对顺序保持不变且长度最长。最长子序列问题是计算机科学中的一个经典问题,它有许多应用,例如在DNA序列比对中,文本比对中等。在Python中,可以使用动态规划算法来解决最长子序列问题。动态规划算法的基本思想是将问题分解为子问题,并将子问题的解存储在一个表格中,以便后续使用。在解决最长子序列问题时,可以使用一个二维数组来存储子问题的解,然后使用递推公式来计算最长子序列的长度。