หาสตริงซูเปอร์สตริงสั้นที่สุดใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A ของสตริง หาสตริงสั้นที่สุดที่มีทุกสตริงใน A เป็น substring สมมติว่าไม่มีสตริงใน A ที่เป็น substring ของอีกตัวหนึ่ง

ตัวอย่าง

A = ["dbsh","dsbbhs","hdsb","ssdb","bshdbsd"] → "hdsbbhssdbshdbsd"

แนวทางแก้ปัญหา: TSP บนกราฟ Overlap + DP Bitmask

1. คำนวณ overlap graph: graph[i][j] = จำนวนตัวอักษรเพิ่มเติมเมื่อต่อ A[j] หลัง A[i]
   • หา suffix ของ A[i] ที่ match prefix ของ A[j] ยาวที่สุด
2. DP[mask][last] = ความยาวสั้นที่สุดของ superstring ที่มีสตริงตาม mask และจบด้วย last
3. Path reconstruction เพื่อสร้างสตริงจริง

ฟังก์ชัน calc(a,b)

for i=0..len(a)-1:
    if b starts with a.substr(i): return len(b) - len(a) + i
return len(b)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int calc(string& a, string& b) {
        for(int i=0; i