CODEWITHSUNDEEP
stringalgorithmgraph
Vikram Bodicherla
Vikram Bodicherla

Reputation: 7123

Supersequence from a bag of strings

Given a string s, what is the most efficient way of identifying the shortest supersequence of s from a bag of strings? Also, the last character of s should match the last character of the superstring.

Upvotes: 5

Views: 326

Answers (3)

Thomas Ahle
Thomas Ahle

Reputation: 31604

Run through every string in the bag, checking if s is a substring using a fast string search like KMP. Check which of the superstrings is shortest. This is O(Σlength of strings in bag).

If you need to do the search a multiple of times, you can construct a suffix trie for each string in the bag, and merge these. Then you can do lookups in O(|s|).

Upvotes: 0

soulcheck
soulcheck

Reputation: 36767

Unless i misunderstood it, this problem is most certainly in P.

A naive approach would be:

  1. Take all strings in B ending with same character as s. Call this new bag B'. Can be done in O(|B|)
  2. Select all strings that are supersequences of s in the bag B'. It can be done in O(|B'|* max(|z|)) for z in B. Testing if a given string s is a subsequence of another string z can be done in O(|z|)
  3. Select the shortest one of previously found strings (in O(|B'|))

Where |x| means size of x.

You can combine those steps, but it's O(|B| * max(|z|)) anyway.

Upvotes: 2

Per
Per

Reputation: 2624

Assuming the bag doesn't change very often, I would construct a DAWG and search it with A*.

Upvotes: 1

Related Questions