wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

shortest_common_superstring (760B)

      1 # Shortest common superstring
      2 
      3 https://en.wikipedia.org/wiki/Shortest_common_supersequence#Shortest_common_superstring
      4 
      5 Given a set of [words] S, find the shortest [word] containing all words of S as a [factor]
      6 
      7 - [turner1989approximation]
      8 - [gallant1980finding]:
      9   - bounds depending on the length of the input strings
     10   - tractability when all input strings have length 2 (on an unbounded alphabet)
     11   - [NP_hard] even when all strings are [primitive_words] and of length 3 (on an unbounded alphabet)
     12 - [bliznets2015parameterized]
     13 
     14 Can be solved for two strings with [KMP], to know the longest [suffix] of a string which is a [prefix] of the other
     15 
     16 See also: [shortest_common_supersequence], [longest_common_substring]
     17 
     18 Up: [computational_problem] on [words]