Как найти и ранжировать все префиксы в списке строк?

Question

У меня есть список строк, и я хочу найти популярные префиксы. Префиксы отличаются тем, что они встречаются как строки в списке ввода.

Я нашел аналогичный вопрос здесь, но ответы на них направлены, чтобы найти одну наиболее общего префикса: Find *most* common prefix of strings - a better way?

Хотя моя проблема похожа, она отличается тем, что мне нужно найти все популярные префиксы. Или, может быть, сформулировать это немного упрощенно, ранговые префиксы от наиболее распространенных до наименьшего.

В качестве примера, рассмотрим следующий список строк: в Индии, индийский, индийский флаг, бык, задиры, ерунды

Приставки ранг: в - 4 раза Индия - 3 раза бык - 3 раз ... и прочее. Пожалуйста, обратите внимание: внутри, бык, Индия все присутствуют в списке входных данных.

Следующие не являются допустимыми префиксы: Ind бушель буль ... так как они не встречаются в списке ввода.

Какую структуру данных следует искать для моделирования моего решения? Я склонен использовать «trie» с счетчиком на каждом узле, который отслеживает, сколько раз этот узел был затронут во время создания trie.

Все предложения приветствуются. Спасибо.

p.s. - Мне нравится python, и мне бы хотелось, чтобы кто-то мог опубликовать быстрый фрагмент, который мог бы начать меня.

Answer 1

words = [ "in", "india", "indian", "indian", "flag", "bull", "bully", "bullshit"] 

Result = sorted([ (sum([ w.startswith(prefix) for w in words ]) , prefix) for prefix in words])[::-1] 

он проходит через каждое слово в качестве префикса и проверяет, сколько других слов начинается с него, а затем сортирует результат. [:: - 1] просто отменяет этот порядок