मान लीजिए कि हमारे पास दो स्ट्रिंग्स टेक्स्ट 1 और टेक्स्ट 2 हैं, हमें उनके सबसे लंबे सामान्य बाद की लंबाई वापस करनी होगी। एक स्ट्रिंग के बाद मूल स्ट्रिंग से उत्पन्न एक नई स्ट्रिंग है जिसमें कुछ वर्ण शेष वर्णों के सापेक्ष क्रम को बदले बिना हटा दिए जाते हैं। (इसलिए उदाहरण के लिए "अबे" "एबीसीडीई" का परवर्ती है लेकिन "एडीसी" नहीं है)। दो स्ट्रिंग्स का एक सामान्य अनुवर्ती एक ऐसा क्रम है जो दोनों स्ट्रिंग्स के लिए सामान्य है। इसलिए यदि कोई सामान्य अनुवर्ती नहीं है, तो 0 लौटाएं। यदि इनपुट "abcde", और "ace" जैसा है, तो परिणाम 3 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=s का आकार, m :=x का आकार
-
यदि या तो n 0 है, या m 0 है, तो वापस 0
-
s :=खाली स्ट्रिंग, s के साथ संयोजित
-
x :=खाली स्ट्रिंग, x के साथ संयोजित
-
रिट:=0
-
क्रम के मैट्रिक्स डीपी को परिभाषित करें (एन + 1) एक्स (एम + 1)
-
मैं के लिए 1 से n की सीमा में
-
j के लिए 1 से m की सीमा में
-
dp[i, j] :=अधिकतम dp[i, j-1] और dp[i-1, j]
-
अगर s[i] =x[j], तो
-
dp[i, j] :=अधिकतम dp[i, j], 1 + dp[i – 1, j – 1]
-
-
-
-
वापसी डीपी [एन, एम]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestCommonSubsequence(string s, string x) {
int n = s.size();
int m = x.size();
if(!n || !m) return 0;
s = " " + s;
x = " " + x;
int ret = 0;
vector < vector <int> > dp(n + 1, vector <int>(m + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m ; j++){
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(s[i] == x[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.longestCommonSubsequence("abcde", "ace"));
} इनपुट
"abcde" "ace"
आउटपुट
3