Methods of computing square roots: Difference between revisions
en>Nfr-Maat mNo edit summary |
en>OsmanRF34 spam rm |
||
| Line 1: | Line 1: | ||
In [[computer science]], the '''shortest common supersequence problem''' is a problem closely related to the [[longest common subsequence problem]]. Given two sequences '''X''' = < x<sub>1</sub>,...,x<sub>m</sub> > and '''Y''' = < y<sub>1</sub>,...,y<sub>n</sub> >, a sequence '''U''' = < u<sub>1</sub>,...,u<sub>k</sub> > 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 [[subsequence]]s 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 a longest common subsequence (lcs) easily. For example, if '''X'''<math>[1..m] = abcbdab</math> and '''Y'''<math>[1..n] = bdcaba</math>, the lcs is '''Z'''<math>[1..r] = bcba</math>. By inserting the non-lcs symbols while preserving the symbol order, we get the scs: '''U'''<math>[1..t] = abdcabdab</math>. | |||
It is quite clear that <math> 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 problem]]s. | |||
== References == | |||
* {{cite book | first1=Michael R. | last1=Garey | author1-link=Michael R. Garey | first2=David S. | last2=Johnson | author2-link=David S. Johnson | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5 | zbl=0411.68039 | at=p. 228 A4.2: SR8 }} | |||
* {{cite book | last=Szpankowski | first=Wojciech | title=Average case analysis of algorithms on sequences | others=With a foreword by Philippe Flajolet | series=Wiley-Interscience Series in Discrete Mathematics and Optimization | location=Chichester | publisher=Wiley | year=2001 | isbn=0-471-24063-X | zbl=0968.68205 }} | |||
==External links== | |||
* [http://nist.gov/dads/HTML/shortestCommonSuperseq.html Dictionary of Algorithms and Data Structures: shortest common supersequence] | |||
[[Category:Problems on strings]] | |||
[[Category:Combinatorics]] | |||
[[Category:Formal languages]] | |||
[[Category:Dynamic programming]] | |||
Revision as of 15:03, 31 January 2014
In computer science, the shortest common supersequence problem is a problem closely related to the longest common subsequence problem. Given two sequences X = < x1,...,xm > and Y = < y1,...,yn >, a sequence U = < u1,...,uk > 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 a longest common subsequence (lcs) easily. For example, if X and Y, the lcs is Z. By inserting the non-lcs symbols while preserving the symbol order, we get the scs: U.
![[1..m]=abcbdab](https://wikimedia.org/api/rest_v1/media/math/render/svg/a81f42392c43a0b0298789a903338bf76dc97223)
![[1..n]=bdcaba](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c34a14553055e81f2d6a800b4b8a81818503a8b)
![[1..r]=bcba](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b3420b174001e3458f72cfd5121bfc789e03e67)
![[1..t]=abdcabdab](https://wikimedia.org/api/rest_v1/media/math/render/svg/56442a3d6041f3395a6d3c705c0e4d391d5c9b63)
It is quite clear that 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.
References
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534