Эта задача была задана одном из тестовых заданий для Tolstoy Summer Camp.
Напишите, пожалуйста, программу для решения описанной ниже задачи. Используйте любой объектно-ориентированный язык. Программа должна представлять собой один файл. Оцениваться будет не только её работоспособность, но и читабельность кода, эффективность и скорость работы алгоритма.
Наибольшая общая подстрока
Даны K строк, нужно найти их наибольшую общую подстроку.
Формат входных данных
В первой строке записано целое число K (1 ≤ K ≤ 10). Далее приведены исходные K строк. Каждая строка состоит не более чем из 10 000 строчных латинских букв.
Формат выходных данных
Выведите наибольшую общую подстроку.
Примеры:
Входные данные
3 abacaba mycabarchive acabistrue
Выходные данные
cab
Решение на PHP
$input = "3 abacabchgfsjsdfssdasdaasdabaistrs mycabarcistrhive acabistrue"; // parse input $array = array_unique( explode("\n", $input) ); $array = array_diff($array, array("")); unset($array[0]); // get min str $min_str = min($array); unset($array[ array_search($min_str, $array) ]); $search_str = $min_str; $substr = null; $start_pos = 0; $min_str_len = strlen($min_str); while ($start_pos++ != $min_str_len) { while ( strlen($search_str) > strlen($substr) ) { // find substr in array $sub_str_found = 0; foreach ($array as $row) { if (strpos($row, $search_str) !== false) { $sub_str_found = 1; } else { $sub_str_found = 0; break; } } if ($sub_str_found == 1) { $substr = $search_str; break; } else { $search_str = substr($search_str, 0, -1); } } $search_str = substr($min_str, $start_pos); } echo $substr;
