นับลำดับย่อยทั่วไปในสองสตริงใน 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() ซึ่งจะคืนค่าจำนวนเต็มตามจำนวนอักขระในสตริงและเก็บไว้ใน len1 สำหรับ str1 และใน len2 สำหรับ str2

• สร้างอาร์เรย์ 2 มิติเพื่อใช้การเขียนโปรแกรมแบบไดนามิก สมมติว่า arr[len1+1][len2+1]

• เริ่มวนรอบสำหรับ i ถึง 0 จนถึง i น้อยกว่า len1

• Inside loop เริ่มวนซ้ำอีกครั้งสำหรับ 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