मान लीजिए हमारे पास दो स्ट्रिंग्स text1 और text2 हैं, हमें उनकी सबसे लंबी सामान्य सबसीक्वेंस की लंबाई लौटानी है। एक स्ट्रिंग की सबसीक्वेंस मूल स्ट्रिंग से कुछ कैरेक्टर्स को हटाकर बिना शेष कैरेक्टर्स के सापेक्ष क्रम को बदले उत्पन्न एक नई स्ट्रिंग है। (उदाहरण के लिए "abe" "abcde" की सबसीक्वेंस है लेकिन "adc" नहीं)। दो स्ट्रिंग्स की सामान्य सबसीक्वेंस वह सबसीक्वेंस है जो दोनों स्ट्रिंग्स के लिए सामान्य है। इसलिए यदि कोई सामान्य सबसीक्वेंस नहीं है, तो 0 लौटाएं। अगर इनपुट "abcde" और "ace" है, तो परिणाम 3 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
n := s का आकार, m := x का आकार
यदि n 0 है, या m 0 है, तो 0 लौटाएं
s := खाली स्ट्रिंग, s के साथ संयोजित
x := खाली स्ट्रिंग, x के साथ संयोजित
ret := 0
क्रम (n + 1) x (m + 1) का एक मैट्रिक्स dp परिभाषित करें
i को 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]
dp[n, m] लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#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