가장 짧은 공통 수퍼 시퀀스는 주어진 두 시퀀스의 각 요소가 존재하는 시퀀스입니다. 즉, 주어진 두 문자열은 모두 Shortest Common Super-Sequence의 하위 시퀀스라고 말할 수 있습니다.
두 문자열에 공통 문자가 없으면 단순히 연결하여 Super-sequence를 얻을 수 있습니다. 그러나 공통 문자가 있는 경우 먼저 가장 긴 문자열을 찾은 다음 다른 문자열의 추가 문자를 추가해야 합니다.
입력 및 출력
Input: Two strings. “ABCDEF” and “XYDEF” Output: The length of the shortest common super-sequence. Here the super-sequence is “ABCDEFXY”. So the length is 8.
알고리즘
superSeq(str1, str2)
입력: 두 개의 문자열 str1 및 str2.
출력: 슈퍼 시퀀스의 길이를 찾습니다.
Begin m := length of str1 n := length of str2 define table named seqTab of size (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 of seqTab[i-1, j] and seqTab[i, j-1] done done return seqTab[m, n] End
예시
#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; //shortest supersequence length is j else if (!j) supSeqTable[i][j] = i; //shortest supersequence length is 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