Сортировка массива строк так, что подстроки любой другой строки появятся позже

Question

Я хочу найти алгоритм, который может сортировать (или упорядочивать) массив строк так, что если любая строка (скажем, B) является подстрокой любой другой строки (скажем, ABAC), то эта B должна следовать после ABAC. Например:

предположим, что строка:

abc
bc
zef
abcde

, тогда порядок будет:

abcde, 
abc, 
bc 
and zef can come anywhere in the order.

Answer 1

Алгоритмы сортировки основаны на сравнении пар значений. Часто языки программирования позволяют обеспечить встроенный метод сортировки функцией сравнения, которая должна принимать два аргумента и возвращать целочисленное значение, указывающее их относительный порядок (-1, 0 или 1).

Итак, определите компаратор следующим образом:

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

Этот тест подстроки должен сначала проверить длину двух строк, чтобы потенциально избежать сканирования строк. Потому что когда a.length > b.length, то a не может быть подстрокой b . Или вы могли бы также явно написать:

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

Если целевой язык программирования не предлагает такой возможности, то вам следует написать свою собственную функцию сортировки (например, QuickSort) и убедиться, что она может использовать такой компаратор,чтобы (начиная со стандартной реализации) вы заменили:

 if a < b

на:

 if compare(a, b) < 0

... и т. д.

Транзитивность отношения

Предположим на мгновение, что отношение, закодированное в функции сравнения, не является транзитивным, поэтому мы могли бы найти три строки a, b и c, для которых:

• сравнение (a, б) <0 </li>
• сравнить (б, в) <0 </li>
• , а также: сравнить (в, а) <= 0 </li>

Сначала отметьте, чтоэто говорит о длине трех строк:

• сравнить (a, b) <0 означает, что a.length> = b.length
• сравнить (b, c) <0 подразумевает, что b.length> = c.length
• сравнить (c, a) <= 0 означает, что c.length> = a.length

ИзИз первых двух мы заключаем, что a.length> = c.length, и, комбинируя это с третьей, мы можем заключить, что все три строки имеют одинаковую длину.

Итак, теперь мы имеем:

• сравнение (a, b) <0 означает, что a упорядочено в алфавитном порядке до b </li>
• сравнение (b, c) <0 означает, что b упорядочено в алфавитном порядке перед c </li>
• сравнение (c,а) <= 0 подразумевает, что с в алфавитном порядке перед а или равно а. </li>

Это приводит к противоречию. И поэтому мы должны сделать вывод, что отношения переходные.