Дано n (1<=n<=100) масссивов строк. Размер каждого массива 1<=m<=20. Длина каждой строки 5<=t<=400. Необходимо найти для каждого массива строковые паттерны, встречающиеся более чем в X% (1<=Х<=100) строк данного массива. Паттерном для строки считается подстрока длиной не менее, чем 2 символа и не более половины длины строки, которая встречается в данной строке более чем 1 раз, но один и тот же символ строки не должен встречаться более чем в одном вхождении одного и того же паттерна, например в строке s=”abababa” есть паттерн ab,ba,aba, но нет паттерна bab, так как в двух вхождениях этой подстроки aBABaba и abaBABa использован один и тот же символ s[3]. TL=10 секунд.

Ничего умнее полного перебора я не придумал. Я иду по каждой строке и нахожу все подстроки длины 2, складываю их хэши в мультисет, запоминаю номер элемента начала каждой подстроки, нахожу хэши, число вхождений которых более 1, по индесу начала подстроки определяю, есть ли среди них непересекающиеся, потом делаю аналогично для длины 3 и так далее до длины t/2. Очевидно сложность подобной операции не менее O(t^2*log(t)). Среди m массивов полученных паттернов мы собираем еще один multiset и считаем в скольки строках встречался один и тот же паттерн. Если более, чем в Х процентах, то добавляем паттерн в ответ. Итоговая сложность для одного массива O(m*t^2*log(t)+k*log(k)), где k – количество полученных паттернов в m строках одного массива, которое довольно сложно оценить (очевидно, t^2*m>k, но оценка очень грубая). Таким образом сложность решения в целом O(n*(m*t^2*log(t)+k*log(k)))=O(n*m*t^2*log(t)), что немного превышает максимальные ограничения. Как оптимизировать решение?