Решение

Ответ:

Используем формулу LCP(S1…Sn) = LCP(LCP(LCP(S1, S2), S3), ...Sn), где LCP — это самый длинный общий префикс.

Чтобы реализовать эту идею, алгоритм перебирает строки [S1…Sn], разыскивая на каждой итерации i самый длинный общий префикс строк LCP(S1…Si). Когда LCP(S1…Si) становится пустой строкой, алгоритм завершается. В противном случае после n итераций алгоритм возвращает LCP(S1…Sn).