นับ subsequence ร่วมในสองสตริงใน C++

เราได้รับสตริงสองตัว ให้เรียกว่า str1 และ str2 ที่มีตัวอักษร และงานคือคำนวณ subsequence ร่วมในทั้งสองสตริง ในโปรแกรมด้านล่างเราใช้ dynamic programming และสำหรับนั้นเราต้องรู้ว่า dynamic programming คืออะไรและใช้กับปัญหาแบบไหนได้

Dynamic programming approach คล้าย divide and conquer ในการแยกปัญหาย่อยลงไปเรื่อยๆ แต่ต่างจาก divide and conquer ที่ subproblems ไม่ได้แก้แยกกัน แต่ผลลัพธ์ของ subproblems ย่อยเหล่านี้จะถูกจำไว้และนำกลับมาใช้สำหรับ subproblems ที่ซ้ำหรือทับซ้อนกัน

Dynamic programming ใช้กับปัญหาที่สามารถแบ่งเป็น subproblems ที่คล้ายกันได้ เพื่อนำผลลัพธ์กลับมาใช้ใหม่ ส่วนใหญ่อัลกอริทึมเหล่านี้ใช้สำหรับ optimization ก่อนแก้ subproblem ที่มีอยู่ dynamic algorithms จะพยายามตรวจสอบผลลัพธ์ของ subproblems ที่แก้ไปแล้วก่อน คำตอบของ subproblems ถูกรวมกันเพื่อให้ได้คำตอบที่ดีที่สุด

ดังนั้นเราสามารถพูดได้ว่า –

อินพุต – string str1 = "abc"     String str2 = "ab" เอาต์พุต – count is 3

คำอธิบาย – จากสตริงที่กำหนด common subsequences ที่เกิดขึ้นคือ: {'a', 'b', 'ab'}

อินพุต – string str1 = "ajblqcpdz"     String str2 = "aefcnbtdi" เอาต์พุต – count is 11

Common subsequences คือ – จากสตริงที่กำหนด common subsequences ที่เกิดขึ้นคือ: { "a", "b", "c", "d", "ab", "bd", "ad", "ac", "cd", "abd", "acd" }

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• รับสตริงสองตัว ให้เป็น str1 และ str2
• คำนวณความยาวของสตริงด้วย length() เก็บใน len1 สำหรับ str1 และ len2 สำหรับ str2
• สร้างอาร์เรย์ 2 มิติสำหรับ dynamic programming ให้เป็น arr[len1+1][len2+1]
• เริ่มลูป for i จาก 0 ถึง i น้อยกว่า len1
• ในลูป เริ่มลูปอีกที for 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;

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 (int i = 1; i <= n1; i++){
        for (int j = 1; j <= n2; j++){
            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;
}

ตัวอย่าง

If we run the above code we will get the following output –

count is: 51