Блин

Точняк

если бы префикс - я бы за  O(NL) решал

понял, то, что я написал, не будет работать для не префикса

тогда можно бинпоиск и хеши

Решаем для текущей строки. На длину ответа выполнены условия бинпоиска. Начальный отрезок low = 0 - нельзя, high = L - можно.  Хотим понять, можно ли mid = (low + high) / 2. Тогда складываем в хеш таблицу все подстроки других строк длины mid. И ищем в ней все подстроки текущей строки длины mid. Если какой-то не нашлось, то high = mid, иначе low = mid.

Подстрок длины mid суммарно порядка N * L. Бинпоиск за log(L), итого O(N * L * log(L))

не, N*N*Log L

вовне ещё цикл для каждой строки

но можно соптимизировать, да

хотя хз, как именно

Значит опять наврал. Тогда нужно заранее сложить все хеши в хеш таблицу, чтобы не бегать лишний раз. Их будет не более 5*10^6.

да,  один раз сложить все подстроки в хэш-таблицу с пометкой "нашлась в одной строке или "

Хотя человек спросил как решать суффмасом за O(N * L)

Тут нужен @Kirundel

По памяти будет 60 мбайт, еле войдет

Шо, где?

написать stringview

@Kirundel расскажи человеку как решать суфмассивом (он просил одним сообщением ниже) мы не умеем

Сначала смержим все строку в одну, через разделитель
Давай построим LCP и по очереди решим задачу для каждой строки.
Теперь давай переберем суффикс, с которого начинается искомая подстрока.
Давай найдем ближайшие "слева" и "справа" (в порядке суфмаса, т.е. лексикографическом) суффиксы, относящиеся к другим строкам. пусть наш LCP  с ними - k1, k2.
Тогда мы не можем взять от нас ни один префикс длины max(k1, k2) или меньше, а вот префикс длины max(k1, k2) + 1 подойдет