UniLecs #Task. Longest Common Prefix
Задача: необходимо реализовать алгоритм поиска наибольшего общего префиска среди массива строк.
Входные данные: массива строк, размер массива до 10⁵.
Вывод: наибольший общий префикс. В случае, если общего префикса нет, вывести пустую строку.
Пример:
1. [ “start”, “stop”, “station” ]
Output: “st”
2. [ “start”, “stop”, “restart” ]
Output: “”
Разбор
Существует несколько различных подходов к решению этой задачи, например, бинарный поиск и модификации на его основе. Попробуйте самостоятельно реализовать такие алгоритмы.
Сегодня же мы рассмотрим, пожалуй, самый простой и интуитивно понятный способ, так называемый горизонтальный: будем последовательно перебирать строки в массиве и находить общий префикс для них, таким образом, к концу прохода по массиву мы либо найдем наибольший общий префикс, либо на одной из итерации обнаружим, что общего префиска для строк не существует.
Алгоритм:
- Пусть префикс изначально равен первой строке из массива.
- В цикле перебираем строки, начиная со 2й.
- На каждой итерации ищем общую подстроку с текущим префиксом и текущей строкой из массива.
- Если находим общую подстроку для текущей строки, переходим к след.элементу массива, в противном случае возвращаем пустую строку и выходим из цикла.
- После полного прохода по массиву мы получим наибольший общий префикс для входного массива строк.
Реализация
https://gist.github.com/unilecs/41b2a34a85cadc660742e95171424323
