資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中計算兩個字串的公共子序列
給定兩個字串，假設為 str1 和 str2，它們包含字元，任務是計算這兩個字串中的公共子序列。在下面的程式中，我們使用動態規劃，為此我們需要了解什麼是動態規劃以及它可以用於哪些問題。
動態規劃方法類似於分治法，它將問題分解成越來越小的子問題。但與分治法不同的是，這些子問題不是獨立解決的。相反，這些較小子問題的結果會被記住並用於類似或重疊的子問題。
動態規劃用於存在可以分解成類似子問題的問題，以便可以重用其結果。通常，這些演算法用於最佳化。在解決手頭的子問題之前，動態演算法會嘗試檢查先前解決的子問題的結果。子問題的解決方案被組合起來以獲得最佳解決方案。
所以我們可以說 -
Input − string str1 = “abc” String str2 = “ab” Output − count is 3
解釋 - 從給定的字串中形成的公共子序列為：{‘a’, ‘b’ , ‘ab’}。
Input − string str1 = “ajblqcpdz” String str2 = “aefcnbtdi” Output − count is 11
公共子序列是 - 從給定的字串中形成的公共子序列為：{“a”, “b”, “c”, “d”, “ab”, “bd”, “ad”, “ac”, “cd”, “abd”, “acd” }
下面程式中使用的步驟如下
輸入兩個字串，假設為 str1 和 str2。
使用 length() 函式計算給定字串的長度，該函式將根據字串中的字元數返回一個整數值，並將其儲存在 str1 的 len1 和 str2 的 len2 中。
建立一個二維陣列來實現動態規劃，假設為 arr[len1+1][len2+1]
開始迴圈，從 i=0 到 i 小於 len1
在迴圈內部，開始另一個迴圈，從 j=0 到 j 小於 len2
在迴圈內部，檢查 IF str1[i-1] = str2[j-1]，然後設定 arr[i][j] = 1 + arr[i][j-1] + arr[i-1][j]
否則，則設定 arr[i][j] = arr[i][j-1] + arr[i-1][j] = arr[i-1][j-1]
返回 arr[len1][len2]
列印結果。
示例
#include <iostream>
using namespace std;
// To count the number of subsequences in the string
int countsequences(string str, string str2){
int n1 = str.length();
int n2 = str2.length();
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++){
for (int j = 0; j <= n2; j++){
dp[i][j] = 0;
}
}
// for each character of str
for (int i = 1; i <= n1; i++){
// for each character in str2
for (int j = 1; j <= n2; j++){
// if character are same in both
// the string
if (str[i - 1] == str2[j - 1]){
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
}
else{
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
}
}
}
return dp[n1][n2];
}
int main(){
string str = "abcdejkil";
string str2 = "bcdfkaoenlp";
cout <<"count is: "<<countsequences(str, str2) << endl;
return 0;
}示例
如果我們執行上述程式碼，我們將得到以下輸出 -
count is: 51
512 次檢視
