Эта задача была задана одном из тестовых заданий для Tolstoy Summer Camp.
Напишите, пожалуйста, программу для решения описанной ниже задачи. Используйте любой объектно-ориентированный язык. Программа должна представлять собой один файл. Оцениваться будет не только её работоспособность, но и читабельность кода, эффективность и скорость работы алгоритма.
Наибольшая общая подстрока
Даны K строк, нужно найти их наибольшую общую подстроку.
Формат входных данных
В первой строке записано целое число K (1 ≤ K ≤ 10). Далее приведены исходные K строк. Каждая строка состоит не более чем из 10 000 строчных латинских букв.
Формат выходных данных
Выведите наибольшую общую подстроку.
Примеры:
Входные данные
3
abacaba
mycabarchive
acabistrue
Выходные данные
Решение на 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;