Content deleted Content added
→Superstring: reverse subsentences to answer clarification request; I feel that computing a minimal-length superstring could be NP-hard, but don't have a supporting citation |
→Superstring: own paragraph for perm. |
||
Line 54:
== Superstring ==
A '''superstring''' of a finite set <math>P</math> of strings is a single string that contains every string in <math>P</math> as a substring. For example, <math>\text{bcclabccefab}</math> is a superstring of <math>P = \{\text{abcc}, \text{efab}, \text{bccla}\}</math>, and <math>\text{efabccla}</math> is a shorter one. Concatenating all members of <math>P</math>, in arbitrary order, always obtains a trivial superstring of <math>P</math>. Finding superstrings whose length is as small as possible is a more interesting problem.
A string that contains every possible permutation of a specified character set is called a [[superpermutation]]. == See also ==
| |||