Найти общую подстроку в строках

[WorldMaster]

Здравствуйте.
Есть списки слов вида:

завладение
завладел
завладела
завладело
завладели
завладев
завладевая
овладев
овладевая

Нужно найти общую подстроку для всех слов.
В данном случае будет "владе".

Чтото никак не могу сообразить эффективный алгоритм. Может кто нибудь знает как можно это решить быстренько.

[Аватар]

https://e-maxx.ru/algo/suffix_automata

[WorldMaster]

Сообщение от Аватар

https://e-maxx.ru/algo/suffix_automata

прикольно конечно .. а реализации есть какие нибудь?

[Arigato]

Нужно чтобы быстро работало? Потому что можно решить в лоб, неэффективно, зато просто.

[WorldMaster]

Сообщение от Arigato

Нужно чтобы быстро работало? Потому что можно решить в лоб, неэффективно, зато просто.

Ну подскажите как? Именно для множества строк а не только для двух.

[Arigato]

Сообщение от WorldMaster

Именно для множества строк а не только для двух.

Для двух строк находим общую подстроку. Далее находим общую подстроку для этой подстроки и третьей строки. Повторяем по всем строкам.

Есть нюанс, общих подстрок у двух строк может быть несколько. Следовательно такое надо проделывать с каждой общей подстрокой. Тут может помочь рекурсия, ну или просто их в стек загонять.

Это самое простое решение в лоб. Оно нерационально и может быть довольно затратно по ресурсам.

[ViktorR]

Могу предложить версию поиска, но вот насколько она подходит, хз.
Идея:
1. Найти минимальное слово из группы - контрольное слово.
2. Всем словам в группе добавить префиксы и постфиксы (расширить слова).
Длина префикса и постфикса - это длина минимального слова - 1.
3. Выполняем корреляционный поиск.
а) Посимвольно вычитаем значение символа слова и символа контрольного слова.
б) разность по модулю суммируем
в) ищем минимальную сумму и позицию контрольного слова
г) формируем подстроку из символов, которые начинаются с позиции контрольного слова и составляют нулевую разность с символами контрольного слова.
4. Собираем подстроки в список (массив)
5. Находим минимальную подстроку.

PS: На примере вашей группы слов написал решение на Питоне.
Я не программист, просто попробовал, так что если что не ругайте
Текст скрипта и файл с набором слов вашего примера во вложении.

[MihalNik]

1. Для слов можно попробовать пойти от максимина сумм минимумов до краев слова у общих букв. У примера в #1 для {в, л, а, д, е} максимально возможные подстроки в 7 букв.
2. Далее можно искать в порядке минимума суммарного числа общих букв. Тогда будет поиск от "д". Или по наиболее "средней", тогда от а (по 3 справа и слева). Или просто с первой, тогда "в".
а) В проходе или его конце надо учесть поглощение других максиминов из п1.
б) Или построить какое-то другое правило, например, если общая буква единственная то без нее распад строки на подстроки, берется минимакс. Например, для поиска от "д" это будет "овла", она короче чем "владе" значит, максимальная строка уже найдена. Простая эвристика может сработать не всегда, но всегда можно вернуться к перебору вариантов из п1. Лучше посмотреть статистику отсеянного эвристикой.

Еще легко ускорить обрезкой необщих букв по краям.

[Аватар]

Набросок с суффиксным автоматом

[WorldMaster]

Спасибо всем за оперативную помощь. Буду разбираться дальше. ))