Найти самую длинную строку, которая является подстрокой всех слов
Требуется написать программу, которая принимает несколько слов, и нам нужно найти то, которое чаще всего повторяется. Подскажите, есть ли какие-нибудь функции? А то понятия не имею как это написать
Пример ввода: Sample Samplin SamplingsFun Saplingdsajisfasfijoi
Пример вывода: Sampl
Ответы (1 шт):
Судя по вашему вопросу ваш преподаватель не ждет от вас использование каких-либо "готовых функций". Это классическая задача на алгоритмы. Она сводится к нахождению общей подстроки попарно между всеми имеющимися строками. Алгоритм примерно такой:
- Берете первые 2 слова (обозначим их длины x1 и x2) и строите матрицу (двумерный массив) размером x1+1 на x2+1
- Заполняете первый столбец матрицы нулями
- Заполняете первую строку матрицы нулями
- Заполняете клетки на пересечении разных букв нулями
- Заполняете клетки на пересечении одинаковых букв значением равным значению на пересечении двух предыдущих индексов плюс 1 (то есть если сейчас вы смотрите индексы 5 и 7 и в заголовках этих двух индексов одинаковые буквы, то вы берете значение из клетки 4 и 6 и прибавляете к нему 1 и результат записываете в клетку с индексом 5 и 7)
Все пункты с 2 по 5 само собой делаются за один раз в двух вложенных циклах. После чего ваша таблица для первой пары слов готова.
- Находите в полученной матрице самое большое число...
- ...и двигаясь по диагонали от него ( каждый раз уменьшая оба индекса на единицу переписываете посимвольно любой из заголовков матрицы - это и есть повторяющиеся символы в этой паре строк)
В итоге после сравнения первых двух слов у вас есть общая строка для этой пары, третью строку можно уже сравнивать с полученной подстрокой и тем самым уточнить полученный результат и так далее. Но нужно учитывать, что подстрок может оказаться несколько и тогда лучше отслеживать все варианты - лишние в ходе проверок сами должны отсеяться.
P.S.: Задача на столько типовая, что по ней и ей подобным есть целый ворох статей в вики, главное правильно сформулировать вопрос!