ลำดับร่วมสั้นที่สุด (Shortest Common Super Sequence)

บทนำ

ลำดับร่วมสั้นที่สุด (Shortest Common Super Sequence - SCS) คือลำดับที่มีองค์ประกอบของทั้งสองลำดับที่กำหนดให้ครบถ้วน กล่าวอีกนัยหนึ่ง สตริงทั้งสองที่กำหนดให้เป็น subsequence ของ SCS

เมื่อสตริงสองตัวไม่มีตัวอักษรร่วมกัน สามารถนำมาต่อกันได้เลยเพื่อให้ได้ Super-sequence แต่เมื่อมีตัวอักษรร่วมกัน จะต้องหาสตริงที่ยาวที่สุดก่อน แล้วจึงเพิ่มตัวอักษรพิเศษของอีกสตริงหนึ่งเข้าไป

อินพุตและเอาต์พุต

Input: สตริงสองตัว "ABCDEF" และ "XYDEF"
Output: ความยาวของ shortest common super-sequence
ที่นี่ super-sequence คือ "ABCDEFXY" ดังนั้นความยาวคือ 8

อัลกอริทึม

superSeq(str1, str2)
Input: สตริงสองตัว str1 และ str2
Output: ความยาวของ super sequence

Begin
    m := ความยาวของ str1
    n := ความยาวของ str2
    กำหนดตาราง seqTab ขนาด (m+1 x n+1)
    for i := 0 to m, do
        for j := 0 to n, do
            if i = 0, then
                seqTab[i, j] := j
            else if j = 0, then
                seqTab[i, j] := i
            else if str1[i-1] = str2[j-1], then
                seqTab[i, j] := 1 + seqTab[i-1, j-1]
            else
                seqTab[i, j] := 1 + minimum ของ seqTab[i-1, j] และ seqTab[i, j-1]
        done
    done
    return seqTab[m, n]
End

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

#include <iostream>
using namespace std;

int min(int a, int b) {
    return (a < b) ? a : b;
}

int superSeq(string str1, string str2) {
    int m = str1.size();
    int n = str2.size();
    int supSeqTable[m+1][n+1];
    
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (!i)
                supSeqTable[i][j] = j;  // ความยาว supersequence สั้นที่สุดคือ j
            else if (!j)
                supSeqTable[i][j] = i;  // ความยาว supersequence สั้นที่สุดคือ i
            else if (str1[i-1] == str2[j-1])
                supSeqTable[i][j] = 1 + supSeqTable[i-1][j-1];
            else
                supSeqTable[i][j] = 1 + min(supSeqTable[i-1][j], supSeqTable[i][j-1]);
        }
    }
    return supSeqTable[m][n];
}

int main() {
    string first = "ABCDEF";
    string second = "XYDEF";
    cout << "Length of the shortest supersequence is " << superSeq(first, second);
}

ผลลัพธ์

Length of the shortest supersequence is 8