Как найти наиболее часто встречающиеся подстроки в строке, используя Bash?

Question

Как найти наиболее часто встречающиеся подстроки в строке, используя Bash?

Пожалуйста, как решить следующую проблему:

Как найти наиболее часто встречающиеся подстроки в данной строке? Например строка:

acd0a55b171241cc13afc7135acd09d609f9e4928e18908e6f6fb5574b4ac13731f993031a13f

В этой строке есть подстроки acd0 а также c13, Также подстрока 13 и больше.

Как найти все появляющиеся подстроки, ранжированные по количеству символов в нем?

Например:

acd0: 4 символа 2 раза

c13: 3 символа 2 раза

13: 2 персонажа 2 раза!

На самом деле 13 появляется 4 раза, но уже дважды c13 и, следовательно, не допускается повторного подсчета.

Решение должно быть в Bash.

1

bash algorithm combinations string-algorithm

Источник

user7156109 14 ноя '16 в 10:15

1 ответ

Другие вопросы по тегам bash algorithm combinations string-algorithm

user3722896 14 ноя '16 в 10:43 2016-11-14 10:43 · Answer 1 · 2016-11-14 10:43

Вам нужно создать суффиксное дерево. Это дерево, которое содержит все повторяющиеся подстроки данной строки.

Наиболее эффективным алгоритмом для создания суффиксного дерева является алгоритм Укконена

Дополнительная информация: Быстрый поиск строк с суффиксными деревьями

В Интернете есть несколько реализаций этого алгоритма для C++ и python. Я не уверен, что было бы легко написать это непосредственно в bash, но вы можете попробовать.