Надо написать на PHP

Question

Наибольшая общая подстрока 
 
Даны K строк, нужно найти их наибольшую общую подстроку. 
 
Формат входных данных 
 
В первой строке записано целое число K (1 ≤ K ≤ 10). Далее приведены исходные K строк. Каждая строка состоит не более чем из 10 000 строчных латинских букв. 
 
Формат выходных данных 
 
Выведите наибольшую общую подстроку. 
 
Примеры: 
 
Входные данные 
 
3 
 
abacaba 
 
mycabarchive 
 
acabistrue 
 
Выходные данные 
 
cab

Андрей Кириченко · Accepted Answer

надо - пиши, не умеешь - оговаривай бюджет, задача нетривиальная

Наурызбай Нагметов · Answer

Берешь эти K строк. Сортируешь по возрастанию длины. Таким образом первая - самая короткая из всех. При этом эта первая строка - это максимально возможная (возможная, подчеркну) подстрока всех остальных. 
 
Теперь погнали. Проверяем, есть ли строка 1 внутри строк 2, 3, ..K. Если есть во всех из них - ответ получен. Если нет - выделяем из строки 1 подстроку длиной на 1 меньше, т. е. отбрасываем первую/последнюю буквы. Снова сверяем эту образованную подстроку со строками 2..K. Если не нашлось решения, отбрасываем уже 2 символа из первой строки - 2 с начала, 2 с конца, по 1 с начала и конца и т. д.