Shortest Common Supersequence Matching Task

A Shortest Common Supersequence Matching Task is a String Matching Task that is required to locate a Shortest Common Supersequence.

• • …
• Counter-Example(s):
  • a Longest Common Subsequence Matching Task.
• See: Shortest Common Substring Matching Task, Shortest Common Superstring Matching Task.

---

---

References

2012

• http://en.wikipedia.org/wiki/Shortest_common_supersequence
  • QUOTE: In computer science, the shortest common supersequence problem is a problem closely related to the longest common subsequence problem. Given two sequences X = < x₁,...,x_m > and Y = < y₁,...,y_n >, a sequence U = < u₁,...,u_k > is a common supersequence of X and Y if U is a supersequence of both X and Y. In other words, the shortest common supersequence between strings x and y is the shortest string z such that both x and y are subsequences of z.

    The shortest common supersequence (scs) is a common supersequence of minimal length. In the shortest common supersequence problem, the two sequences X and Y are given and the task is to find a shortest possible common supersequence of these sequences. In general, the scs is not unique.

    For two input sequences, an scs can be formed from an lcs easily. For example, if X[math]\displaystyle{ [1..m] = abcbdab }[/math] and Y[math]\displaystyle{ [1..n] = bdcaba }[/math], the lcs is Z[math]\displaystyle{ [1..r] = bcba }[/math]. By inserting the non-lcs symbols while preserving the symbol order, we get the scs: U[math]\displaystyle{ [1..t] = abdcabdab }[/math].

    It is quite clear that [math]\displaystyle{ r + t = m + n }[/math] for two input sequences. However, for three or more input sequences this does not hold. Note also, that the lcs and the scs problems are not dual problems.

---