Advanced Fruits
এই প্রবলেমটি একটি স্ট্রেইট ফরোয়ার্ড Shortest Common Subsequence প্রবলেম। ডিরেক্ট Shortest Common Subsequence Algorithm প্রয়োগ করে কিংবা Longest Common Subsequence কে কিছুটা মডিফিকেশন করে এটি সলভ করা সম্ভব। ডাইনামিক প্রোগ্রামিংয়ের খুবই জনপ্রিয় এবং ক্লাসিক্যাল দুটি এলগরিদম হলো LCS ও SCS Algorithm । LCS বা SCS Algorithm কিভাবে কাজ করে তুমি যদি না জেনে থাকো তাহলে নিচের লিঙ্ক থেকে শিখে নিতে পার । খুব সহজ ভাষায় LCS হলো দুটি স্ট্রিংয়ের মধ্যে সবচে longest subsequece টি. দুটি স্ট্রিংয়ের lcs একটির বেশীও হতে পারে। যেমন – eye, eyes স্ট্রিং দুটির longest subsequence হলো eye. উইকিতে Shortest Common Subsequence এর বর্ণনা করা হয়েছে এভাবে – a shortest common supersequence of strings x and y is a shortest string z such that both x and y are subsequences of z. যেমন – স্ট্রিং ananas ও banana এর SCS হলো bananas। লক্ষ করো ডেসক্রিপশন অনুযায়ী bananas এর subsequence স্ট্রিং হলো ananas, banana । আবার ananas ও banana এর lcs হলো anana. রেজাল্টিং lcs এর সাথে যেসব ক্যারেক্টার lcs এর অংশ না, সেগুলো জুড়ে দিলেই scs পেয়ে যাবে । anana-র সাথে char b ও s যোগ করে দেখো; কাঙ্ক্ষিত Shortest Common Subsequence – bananas পেয়ে যাবে।
এবার মূল সমস্যায় ফিরে আসা যাক। এই সমস্যাটি সমাধান করার জন্য প্রথমে স্ট্রিং দুটির LCS বের করতে হবে । তারপর স্ট্রিং দুটিকে মার্জ করে নিলেই SCS পাওয়া যাবে। খেয়াল রাখতে হবে, যেসব ক্যারেক্টার ম্যাচ করেছে মানে LCS এর ক্যারেক্টারগুলো যেন আউটপুটে একবারের বেশী না আসে।
সলভিং এপ্রোচ স্টেপ বাই স্টেপ
১। স্ট্রিং দুটির LCS বের করতে হবে।
২। একটা ক্যারেক্টার টাইপ ভেক্টর ডিক্লেয়ার করে নাও। এই ভেক্টরের মাঝে যে ক্যারেক্টারগুলো স্ট্রিং দুটিতে ম্যাচ করে অর্থাৎ যেসব ক্যারেক্টার LCS এর পার্ট সেগুলোকে জমা রাখবো।
৩। ম্যাচিং ক্যারেক্টারগুলোকে খুঁজে বের করার জন্য ব্যকট্র্যাক চালাও। এবং করেস্পন্ডিং ক্যারেক্টারগুলো ক্যারেক্টার টাইপ ভেক্টরটিতে পুশ করো।
৪। ক্যারেক্টার ভেক্টরে লুপ ঘুরাও এবং দুটি স্ট্রিং ট্রাভার্স করে রেজাল্টেন্ট ক্যারেক্টারগুলো প্রিন্ট দাও।
হাতে-কলমে ম্যানিপুলেশন</span>
apple peach
Here, s1 = apple, and s2 = peach. LCS will be 2 here. And corresponding characters are ‘p’ and ‘e’, as shown. apple and peach. So, we will get two character at char vector. Thus, the two given string will have below value.
1
2
s1Arr = false | false | true | false | true
s2Arr = true | true | false | false | false
| vector<char> vc; | |
| char s1[1005] , s2[1005]; | |
| int dp[105][105]; | |
| void backtrace(int i, int j) | |
| { | |
| if(i == 0 || j == 0) | |
| return; | |
| else if(s1[i-1] == s2[j-1]) { | |
| backtrace(i-1, j-1); | |
| vc.push_back(s1[i-1]); | |
| } | |
| else { | |
| if(dp[i][j-1] > dp[i-1][j]) | |
| backtrace(i, j-1); | |
| else | |
| backtrace(i-1, j); | |
| } | |
| } | |
| /// finding lcs of s1 and s2 whose lengths are len1 and len2 respectively | |
| /// LCS is stored in the vector "vc" | |
| void lcs() | |
| { | |
| int n = strlen(s1); | |
| int m = strlen(s2); | |
| memset(dp, 0, sizeof(dp)); | |
| for(int i=0; i<=n; ++i) dp[i][0] = 0; //base cases | |
| for(int i=0; i<=m; ++i) dp[0][i] = 0; //base cases | |
| // filling up dp[][] table for LCS | |
| for(int i=1; i<=n; ++i) | |
| { | |
| for(int j=1; j<=m; ++j) | |
| { | |
| if(s1[i-1]==s2[j-1]) | |
| dp[i][j] = 1 + dp[i-1][j-1]; | |
| else | |
| dp[i][j] = max(dp[i-1][j], dp[i][j-1]); | |
| } | |
| } | |
| } | |
| int main() | |
| { | |
| while(scanf("%s %s", s1, s2) == 2) | |
| { | |
| vc.clear(); | |
| int len1 = strlen(s1); | |
| int len2 = strlen(s2); | |
| lcs(); | |
| backtrace(len1, len2); //getting LCS by backtracing | |
| int l1 = 0, l2 = 0; | |
| /// then printing SCS of s1 and s2 with the help of LCS of s1 and s2 | |
| for(int i=0; i<vc.size(); ++i) { | |
| while(l1 < len1 && s1[l1] != vc[i]) { | |
| cout << s1[l1]; | |
| ++l1; | |
| } | |
| while(l2 < len2 && s2[l2] != vc[i]) { | |
| cout << s2[l2]; | |
| ++l2; | |
| } | |
| cout<<vc[i]; | |
| ++l2, ++l1; | |
| } | |
| while(l1<len1) | |
| cout<<s1[l1++]; | |
| while(l2<len2) | |
| cout<<s2[l2++]; | |
| cout<<endl; | |
| } | |
| return 0; | |
| } |
LCS Learning লিঙ্ক
- https://www.youtube.com/watch?v=NnD96abizww&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&index=27
- http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/