Определение наилучшей структуры данных для проблемы с точки зрения сложности

Question

Итак, я обнаружил следующую проблему, предложенную несколько лет назад на олимпиаде по программированию в Румынии:

Скажем, у вас есть язык с ровно N словами. Два слова называются K-подобными, если они имеют одинаковые первые буквы K, а буква k + 1 отличается.

Степень сходства между T-словами называется K, если любые два слова K-подобны, но не (K + 1) -подобны.

Учитывая М случайных слов, определить степень сходства между ними.

Мне было интересно, какова структура данных, которая была бы наилучшей с точки зрения сложности для реализации этой программы.

Я пытался реализовать это, используя массивы строк или массивы массивов символов.

Пример: для asdf, asdffff и asdg степень подобия должна быть 3.

Answer 1

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

Начните с первых двух слов "asdf" и "adsffff". Сравните символ за символом, пока не найдете несоответствие. В итоге вы получите обычные буквы "asdf".

Затем сравните следующее слово с результатом этого сравнения. Вы сравниваете «asdf» с «asdg» и обнаруживаете несоответствие 4-го символа, поэтому ваш самый длинный общий префикс теперь - «asd».

Вы можете продолжить таким образом через все слова в вашем списке. И если вы встретите слово, начинающееся с чего-либо, кроме «а», то ваш самый длинный общий префикс будет 0, и вы сможете выйти.

Исходя из вашего вопроса и разъяснений в комментариях, вышеизложенное решит проблему. Однако я все еще думаю, что ваше понимание проблемы неверно.