মডিউল ২২_৬ঃ Printing LCS Approach

মডিউল ২২_৫ এ দেখানো ইনপুটির জন্য Printing LCS Approach দেখবো।

যেহেতু ক্যারেক্টার ২ টি মিলে গেছে সেজন্য ক্যারেক্টারটিকে store করে রাখবো এবং ইনডেক্স i-1, j-1 এ চলে যাব।

যেহেতু ক্যারেক্টার ২ টি অমিল তাই সেই ক্যারেক্টারটিকে store করবো নাহ। আমরা movement করবো

dp[i-1][j] এবং dp[i][j-1] এর মধ্যে যেইটির মান বড় সেই ইনডেক্স এ movement করা হবে । যদি dp[i-1][j] এবং dp[i][j-1] এর মধ্যে মান সমান হয় তাহল যেকোন এক দিকে movement করলে হবে।

যেহেতু ক্যারেক্টার ২ টি মিলে গেছে সেজন্য ক্যারেক্টারটিকে store করে রাখবো এবং ইনডেক্স i-1, j-1 এ চলে যাব।

যেহেতু ক্যারেক্টার ২ টি মিলে গেছে সেজন্য ক্যারেক্টারটিকে store করে রাখবো এবং ইনডেক্স i-1, j-1 এ চলে যাব।

যেহেতু ক্যারেক্টার ২ টি অমিল তাই সেই ক্যারেক্টারটিকে store করবো নাহ। আমরা movement করবো

dp[i-1][j] এবং dp[i][j-1] এর মধ্যে যেইটির মান বড় সেই ইনডেক্স এ movement করা হবে । যদি dp[i-1][j] এবং dp[i][j-1] এর মধ্যে মান সমান হয় তাহল যেকোন এক দিকে movement করলে হবে।

যেহেতু ক্যারেক্টার ২ টি মিলে গেছে সেজন্য ক্যারেক্টারটিকে store করে রাখবো এবং ইনডেক্স i-1, j-1 এ চলে যাব।

২টি স্ট্রিং অথবা যেকোন একটি স্ট্রিং শেষ হয়ে গেলে কায্যক্রম অফ করে দিব।

এখন store করা ক্যারেক্টার গুলোর স্ট্রিংটি হলঃ "feda" , সেইটিকে reverse করলে "adef" পাবে সেইটিই Longest Common Subsequence হবে।

Last updated