ค้นหา Superstring ที่สั้นที่สุดใน C++

สมมติว่าเรามีอาร์เรย์ A ของสตริง เราต้องหาสตริงที่เล็กที่สุดที่มีแต่ละสตริงใน A เป็นสตริงย่อย นอกจากนี้เรายังสามารถสรุปได้ว่าไม่มีสตริงใดใน A เป็นสตริงย่อยของสตริงอื่นใน A.

ดังนั้น หากอินพุตเป็น ["dbsh","dsbbhs","hdsb","ssdb","bshdbsd"] เอาต์พุตจะเป็น "hdsbbhssdbshdbsd"

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

• กำหนดฟังก์ชัน calc() ซึ่งจะใช้เวลา a, b,

• สำหรับการเริ่มต้น i :=0, เมื่อ i

  • หากสตริงย่อยของ a จากดัชนี i ถึงจุดสิ้นสุดอยู่ที่จุดเริ่มต้นของ b แล้ว −

    • ขนาดส่งคืนของ b - ขนาดของ a + i

• ขนาดส่งคืนของ b

• จากวิธีหลัก ทำตามขั้นตอนเหล่านี้

• ret :=สตริงว่าง

• n :=ขนาดของ A

• กำหนดกราฟอาร์เรย์ 2 มิติขนาด n x n -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • กราฟ[i, j] :=calc(A[i], A[j])

    • กราฟ[j, i] :=calc(A[j], A[i])

• กำหนดขนาดอาร์เรย์ dp:2^n x n.

• กำหนดเส้นทางอาร์เรย์ขนาด:2^n x n.

• minVal :=inf

• สุดท้าย :=-1

• สำหรับการเริ่มต้น i :=0 เมื่อ i <2^n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • dp[i, j] :=inf

• สำหรับการเริ่มต้น i :=0 เมื่อ i <2^n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า i AND 2^j ไม่ใช่ศูนย์ ดังนั้น

      • ก่อนหน้า :=i ^ (2^j)

    • ถ้าก่อนหน้าเท่ากับ 0 ดังนั้น −

      • dp[i, j] :=ขนาดของ A[j]

    • มิฉะนั้น

      • สำหรับการเริ่มต้น k :=0 เมื่อ k

        • ถ้าก่อนหน้า AND 2^k และ df[prev,k] ไม่ใช่ inf และ df[prev,k] +graph[k,j]

          • dp[i, j] :=dp[ก่อนหน้า, k] + กราฟ[k, j]

          • เส้นทาง[i, j] :=k

  • ถ้าฉันเหมือนกับ 2^n - 1 และ dp[i, j]

    • minVal :=dp[i, j]

    • สุดท้าย :=j

• สกุลเงิน :=2^n - 1

• กำหนดหนึ่งสแต็ก st

• ในขณะที่ curr> 0, ทำ -

  • ใส่สุดท้ายลงใน st

  • temp :=curr

  • curr :=curr - (2^สุดท้าย)

  • สุดท้าย :=เส้นทาง[ชั่วคราว สุดท้าย]

• ผม :=องค์ประกอบด้านบนของ st

• ลบองค์ประกอบออกจาก st

• ret :=ret + A[i]

• ในขณะที่ (ไม่ใช่ st ว่างเปล่า) ทำ -

  • j :=องค์ประกอบด้านบนของ st

  • ลบองค์ประกอบออกจาก st

  • ret :=ret เชื่อมสตริงย่อยของ A[j] จาก (ขนาดของ A[j] - กราฟ[i,j] ถึงสิ้นสุด)

  • ผม :=เจ

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int calc(string& a, string& b){
      for (int i = 0; i < a.size(); i++) {
         if (b.find(a.substr(i)) == 0) {
            return b.size() - a.size() + i;
         }
      }
      return (int)b.size();
   }
   string shortestSuperstring(vector<string>& A){
      string ret = "";
      int n = A.size();
      vector<vector<int> > graph(n, vector<int>(n));
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            graph[i][j] = calc(A[i], A[j]);
            graph[j][i] = calc(A[j], A[i]);
         }
      }
      int dp[1 << n][n];
      int path[1 << n][n];
      int minVal = INT_MAX;
      int last = -1;
      for (int i = 0; i < (1 << n); i++)
      for (int j = 0; j < n; j++)
      dp[i][j] = INT_MAX;
      for (int i = 1; i < (1 << n); i++) {
         for (int j = 0; j < n; j++) {
            if ((i & (1 << j))) {
               int prev = i ^ (1 << j);
               if (prev == 0) {
                  dp[i][j] = A[j].size();
               } else {
                  for (int k = 0; k < n; k++) {
                     if ((prev & (1 << k)) && dp[prev][k] !=
                     INT_MAX && dp[prev][k] + graph[k][j] < dp[i][j]) {
                        dp[i][j] = dp[prev][k] + graph[k][j];
                        path[i][j] = k;
                     }
                  }
               }
            }
            if (i == (1 << n) - 1 && dp[i][j] < minVal) {
               minVal = dp[i][j];
               last = j;
            }
         }
      }
      int curr = (1 << n) - 1;
      stack<int> st;
      while (curr > 0) {
         st.push(last);
         int temp = curr;
         curr -= (1 << last);
         last = path[temp][last];
      }
      int i = st.top();
      st.pop();
      ret += A[i];
      while (!st.empty()) {
         int j = st.top();
         st.pop();
         ret += (A[j].substr(A[j].size() - graph[i][j]));
         i = j;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"};
   cout << (ob.shortestSuperstring(v));
}

อินพุต

{"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"}

ผลลัพธ์

hdsbbhssdbshdbsd