Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

โปรแกรมค้นหาความยาวของลำดับย่อยทั่วไปที่ยาวที่สุดใน C++


สมมติว่าเรามีสตริง text1 และ text2 สองสตริง เราต้องหาความยาวของลำดับย่อยทั่วไปที่ยาวที่สุด ตามที่เราทราบลำดับย่อยของสตริงคือสตริงใหม่ที่สร้างขึ้นจากสตริงเดิมโดยมีอักขระบางตัวถูกลบโดยไม่เปลี่ยนลำดับสัมพัทธ์ของอักขระที่เหลือ (ตัวอย่างเช่น "abe" เป็นผลสืบเนื่องมาจาก "abcde" แต่ "adc" ไม่ใช่) ลำดับย่อยทั่วไปของสองสตริงคือลำดับย่อยที่เหมือนกันกับทั้งสองสตริง ดังนั้น หากไม่มีลำดับย่อยร่วม ให้คืนค่า 0 หากอินพุตเป็นเหมือน “abcde” และ “ace” ผลลัพธ์จะเป็น 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • n :=ขนาดของ s, m :=ขนาดของ x

  • ถ้า n เป็น 0 หรือ m เป็น 0 ให้คืนค่า 0

  • s :=สตริงว่าง ต่อด้วย s

  • x :=สตริงว่าง ต่อด้วย x

  • ยกเลิก :=0

  • กำหนดเมทริกซ์ dp ของคำสั่ง (n + 1) x (m + 1)

  • สำหรับฉันอยู่ในช่วง 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