4

Statement:

Given an array of strings S. You can make a string by combining elements from the array S (you can use an element more than once)

In some situations, there are many ways to make a certain string from the array S.

Example:

S = {a, ab, ba}

Then there are 2 ways to make the string "aba":

  • "a" + "ba"
  • "ab" + "a"

Question:

Given an array of string S. Find the shortest string such that there are more that one way to make that string from S. If there're none, print out -1.

P/S: I have been thinking for many days but this is the best one I've got so far:

  • Generate all permutations of the array
  • For each permutation, make a string from the array S
  • Check if that string is made before, if yes, print out the string, if not, save that string.

But this algorithm clearly won't pass all the test cases. I can't think of any better algorithm.

גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
unglinh279
  • 675
  • 4
  • 24
  • 1
    Rough idea: Make a trie-automaton thing, then dynamic programming on it to find two different paths that ends in the root node. (where does the problem come from? It looks familiar) – user202729 Oct 24 '21 at 02:59
  • @user202729 what is a trie-automaton thing? i can't find it on google. can you provide a link or something? the problem is from a local contest in my school, i don't really know the source. – unglinh279 Oct 24 '21 at 03:03

2 Answers2

3

Imagine that you have found your string, and you are matching it two different ways with strings from S. You start with two different strings that match the prefix, and then you repeatedly add a string from S to the shorter one until you end up with a matching length. From your example, that's

"ab"
"a"

"ab"
"aba"

"aba"
"aba"

At every step, you have 2 different strings from S that overlap at the end.

Imagine a directed graph where every vertex is a tuple (i,j,t), where i and j are the indexes of the overlapping strings at the end, and t is the number of characters left over at the end of the longer one after the overlapping section. Make it a rule that t >= 0 and that string i is always the one that ends first.

The edges of the graph indicate which vertexes you can get to by adding a new string to the shorter one, with a cost equal to the length of the added string. Of course you can only add a string if it overlaps with the t characters left over on the longer side.

Your task is then to use Dijkstra's algorithm to find the shortest path in this graph, from an initial selection of 2 distinct strings to a pair with t=0. Initially sorting the array of strings will let you use a binary search to find the strings that overlap the required suffix (the longer ones will all be together), which is an effective optimization.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • Could there be an issue with your suggestion to use Dijkstra in that we have unlimited strings to choose from and continually choosing the smallest string to add (which is what Dijkstra would do to prioritise the cost you describe) might lead to a suboptimal solution (or possibly timing out)? – גלעד ברקן Oct 25 '21 at 11:13
  • You don't choose the smallest string to add. You choose all of them that match. Each one leads to a new vertex that goes into the priority queue with its updated total path cost. The total path cost is equal to the sum of lengths added, so shortest path = optimal solution, and Dijkstra's is guaranteed to find it. If there is no solution then you'll eventually stop discovering new vertexes and the queue will empty. – Matt Timmermans Oct 25 '21 at 11:47
  • Oh, my bad, priority is on total cost after the addition. – גלעד ברקן Oct 25 '21 at 11:58
  • Regarding no solution, couldn't there be a degenerate input case of a cycle without end, where matches can continue but there's always some left over? – גלעד ברקן Oct 25 '21 at 12:06
  • 1
    There are at most O(|S|^2 * max_len(strings in S)) reachable vertices, and following Dijkstra, they're only enqueued when you discover a new one or a shorter path to one. – Matt Timmermans Oct 25 '21 at 12:09
  • Thank you for persisting in explaining this to me :) – גלעד ברקן Oct 25 '21 at 12:33
1

Here's an O(N3) algorithm, where N is the total length of each string:

  1. For every element Si in S:
    1. Construct an NFA for the regular expression Si(S1|...|Sn)*
    2. Construct an NFA for the regular expression (S1|...|Si-1|Si+1|...|Sn)(S1|...|Sn)*
    3. Construct an NFA that is the intersection of the NFA in step 1.1 and step 1.2
    4. Find the shortest string accepted by the NFA in step 1.3
  2. Return the shortest string among the strings in step 1.4

The above algorithm can be improved to O(N2logN):

  1. Construct an NFA for the regular expression (S1|...|Sn)*
  2. Construct cross-product of two copies of the NFA in step 1.
  3. For each state in the NFA in step 2, find the shortest string accepted by the NFA from that state.
  4. Let = {S}.
  5. While is not empty:
    1. Take an element T from .
    2. Partition T into P and Q somewhat evenly.
    3. Construct an NFA for the regular expression (P1|...|Pp)(S1|...|Sn)*, reusing the NFA in step 1.
    4. Construct an NFA for the regular expression (Q1|...|Qq)(S1|...|Sn)*, reusing the NFA in step 1.
    5. Construct cross-product of the NFA in step 5.3 and step 5.4, reusing the NFA in step 2.
    6. Find the shortest string accepted by the NFA in step 5.5, reusing the result of step 3.
    7. If P has more than 1 element, put P into .
    8. If Q has more than 1 element, put Q into .
  6. Return the shortest string among the strings in step 5.6

Edit: The following is an O(N2) algorithm, improved from the top answer:

  1. Let T be every suffix of every string of S.
  2. Build a trie out of T.
  3. Let G be a weighted directed graph. The vertices are the elements of T, and the edges are: for each string Si in S and Tj in T, if Si = Tj + D or Tj = Si + D (using the trie in step 2 to find all such pairs), add an edge from D to Tj weighted length of Si.
  4. Find the distance from the empty string to every vertex in G.
  5. For each string Si, Sj in S, if Si != Sj and Si = Sj + D (using the trie in step 2 to find all such pairs), find the distance from the empty string to D (using step 4).
  6. The length of the answer is half of the shortest distance among all distances in step 5. (It's trivial to find the actual answer but I'm too lazy to describe it :p)
johnchen902
  • 9,531
  • 1
  • 27
  • 69