26 lines
814 B
Plaintext
26 lines
814 B
Plaintext
ClearAll[RosettaShortestCommonSuperSequence]
|
|
RosettaShortestCommonSuperSequence[aa_String, bb_String] :=
|
|
Module[{lcs, scs, a = aa, b = bb},
|
|
lcs = LongestCommonSubsequence[aa, bb];
|
|
scs = "";
|
|
While[StringLength[lcs] > 0,
|
|
If[StringTake[a, 1] == StringTake[lcs, 1] \[And] StringTake[b, 1] == StringTake[lcs, 1],
|
|
scs = StringJoin[scs, StringTake[lcs, 1]];
|
|
lcs = StringDrop[lcs, 1];
|
|
a = StringDrop[a, 1];
|
|
b = StringDrop[b, 1];
|
|
,
|
|
If[StringTake[a, 1] == StringTake[lcs, 1],
|
|
scs = StringJoin[scs, StringTake[b, 1]];
|
|
b = StringDrop[b, 1];
|
|
,
|
|
scs = StringJoin[scs, StringTake[a, 1]];
|
|
a = StringDrop[a, 1];
|
|
]
|
|
]
|
|
];
|
|
StringJoin[scs, a, b]
|
|
]
|
|
RosettaShortestCommonSuperSequence["abcbdab", "bdcaba"]
|
|
RosettaShortestCommonSuperSequence["WEASELS", "WARDANCE"]
|