資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢一個字串的最長子序列，該子序列也是另一個字串的子字串
假設我們有兩個字串 X 和 Y，我們需要找到字串 X 的最長子序列的長度，該子序列是字串 Y 的子字串。所以如果 X = “ABCD” 且 Y = “BACDBDCD”，則輸出將為 3。因為 “ACD” 是 X 的最長子序列，並且是 Y 的子字串。
這裡我們將使用動態規劃方法來解決這個問題。所以如果 X 的長度為 n，Y 的長度為 m，則建立一個 (m+1)x(n+1) 階的 DP 陣列。DP[i, j] 的值為 X[0…j] 的最長子序列的長度，該子序列是 Y[0…i] 的子字串。現在對於 DP 的每個單元格，它將遵循如下規則
- 對於 i 從 1 到 m 的範圍
- 對於 j 從 1 到 n 的範圍
- 當 X[i – 1] 與 Y[j – i] 相同，則 DP[i, j] := 1 + DP[i – 1, j – 1]
- 否則 DP[i, j] := 1 + DP[i, j – 1]
- 對於 j 從 1 到 n 的範圍
最後，x 的最長子序列的長度（該子序列是 y 的子字串）是 max(DP[i, n])，其中 1 <= i <= m。
示例
#include<iostream>
#define MAX 100
using namespace std;
int maxSubLength(string x, string y) {
int table[MAX][MAX];
int n = x.length();
int m = y.length();
for (int i = 0; i <= m; i++)
for (int j = 0; j <= n; j++)
table[i][j] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (x[j - 1] == y[i - 1])
table[i][j] = 1 + table[i - 1][j - 1];
else
table[i][j] = table[i][j - 1];
}
}
int ans = 0;
for (int i = 1; i <= m; i++)
ans = max(ans, table[i][n]);
return ans;
}
int main() {
string x = "ABCD";
string y = "BACDBDCD";
cout << "Length of Maximum subsequence substring is: " << maxSubLength(x, y);
}輸出
Length of Maximum subsequence substring is: 3
更新於: 2019-12-18
1K+ 次檢視
廣告