eatmore's blog

Finding lexicographically minimal merge of two strings in linear time
By eatmore, history, 8 years ago, In English

After reading the editorial for RCC Elimination round problem E, I thought of an easier problem of merging two strings such that the result is lexicographically minimal. Formally, a merge of two strings a and b is a string s of length |a| + |b| such that there exist two strictly increasing sequences of indices i1, i2, ..., i|a| and j1, j2, ..., j|b| such that a = si1si2... si|a|, b = sj1sj2... sj|b| and each index in s appears exactly once in i1, ..., i|a|, j1, ..., j|b|.

The above mentioned editorial provides an algorithm for solving this problem that works in time and uses hashes. Actually, this problem can be solved in linear time. The solution works roughly like this: maintain current position pa in a and pb in b. On each step, lexicographically compare the suffix of a starting at pa with the suffix of b starting at pb, and take a character from the suffix that is smaller (actually, for this to work, it is necessary to terminate each string with a character that is greater than any character in the strings, so that if one of the suffixes is a prefix of the other, the shorter suffix is considered larger, not smaller). The author proposes to compare the suffixes by using binary search and hashing, which takes time. However, this can be done in constant time.

Actually, this is a well known Longest Common Extension problem. One of the constant-time solutions is as follows: construct a suffix tree from the strings, then preprocess it using one of Lowest Common Ancestor algorithms that can answer LCA queries in constant time. It is easy to see that the lowest common ancestor of two leaves in a suffix tree that correspond to two suffixes can be used to find the length of the longest common prefix of those suffixes. From that, performing lexicographical comparison is easy.

It is possible to build and preprocess a suffix tree in linear time, so the overall running time is O(n), but the algorithm is quite complex. Does anyone know of a simpler algorithm with the (asymptotically) same running time?

  • Vote: I like it
  • +68
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I know that there is a way of sorting all suffixes of a given string in O(N). Using that it should work. I know about it as it is explained on some Romanian site bu I hadn't tried to understand. However, I can say just that it is easier than building a suffix tree (from the size of the article)

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Maybe I have a simple way to do it in O(NC), where C denote the alphabeta size.

Suppose the string s and t are something like

a = xxxxy b = xxxxxz

If x < y z, you may definitly take all x first,

if y < x < z, you may take the string with the smaller character after x.

if x > y z, and the number of x is different, you may take the shorter one. in case the number of x is equal, you should consider the same situation after the x in each string. But note that y and z are smaller than x, which means this recursive steps are bounded by the size of alphabeta.

In each case, what you want is the next different character and the number of same character start from some positions. By simple precalculating, you may do it in linear time.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not that easy. Suppose that both strings start with something like zzzxyxyxyxy, where x < y < z. In this case, it will be necessary to scan through all these xy repetitions, and the number of these repetitions can be much bigger than the alphabet size.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right, I underestimate the difficulty in the third case :( .

      → Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

By the way, your problem was used in SRM, but here you can even do O(N2).

→ Reply