Sorting array of strings such that substrings of any other string will comes later

user_11951637 0
Viewed 70

I want to find an algorithm which can sort (or arrange) array of the strings such that if any string (say B) is sub-string of any other string (say ABAC) than that B should come after ABAC. e.g. :

suppose the string are :

abc
bc
zef
abcde

then order will be :

abcde, 
abc, 
bc 
and zef can come anywhere in the order.
optimization sorting algorithm string
1 Answers

Sort algorithms are based on comparing pairs of values. Often programming languages allow to provide the built-in sort-method with a comparator function, which should take two arguments, and return an integer value indicating their relative order (-1, 0 or 1).

So define the comparator as follows:

compare(a, b):
    if a is substring of b then return 1
    if b is substring of a then return -1
    if a < b then return -1
    if a > b then return 1
    return 0

This substring-test should first check the length of the two strings to potentially avoid a scan of the strings. Because when a.length > b.length, then a cannot be a substring of b. Or you could also explicitly write:

compare(a, b):
    if a.length <= b.length and a is substring of b then return 1
    if a.length >= b.length and b is substring of a then return -1
    if a < b then return -1
    if a > b then return 1
    return 0

If the target programming language does not offer this possibility, then you should write your own sorting function (like QuickSort), and make sure it can use such a comparator, so that (starting from a standard implementation) you would replace:

 if a < b

with:

 if compare(a, b) < 0

...etc.

Transitivity of the relationship

Let's assume for a moment that the relationship that is encoded in the compare function is not transitive, so that we could find three strings a, b and c for which:

  • compare(a, b) < 0
  • compare(b, c) < 0
  • but also: compare(c, a) <= 0

First, note what this says about the lengths of the three strings:

  • compare(a, b) < 0 implies that a.length >= b.length
  • compare(b, c) < 0 implies that b.length >= c.length
  • compare(c, a) <= 0 implies that c.length >= a.length

From the first two we conclude that a.length >= c.length, and combining that with the third, we can conclude all three strings have the same length.

So now we have:

  • compare(a, b) < 0 implies that a is alphabetically ordered before b
  • compare(b, c) < 0 implies that b is alphabetically ordered before c
  • compare(c, a) <= 0 implies that c is alphabetically ordered before a, or is equal to a.

This leads to a contradiction. And so we must conclude that the relationship is transitive.

user_54598390
Related