Дано 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)), что немного превышает максимальные ограничения. Как оптимизировать решение?
Необходимо найти все паттерны, или хотя бы 1?
Почему нельзя искать паттерны длиной 1 символ, и только их?
Необходимо найти все паттерны длины от 2 до t/2 включительно
ну можно например использовать хеш таблицы, раз ты уже с хешами работаешь, тогда уберутся логарифмические множители из оценки сложности. Еще что-то мне подсказывает что здесь можно заиспользовать суффиксный массив (или автомат).
еще простая идея, не искать все паттерны, а только самые длинные. понятно что все подстроки паттернов также являются паттернами. для простоты подсчета лучше понимать под набором паттернов наидлиннейший и все его суффиксы.
UPD: имелось в виду "и все его префиксы"
Контрпример: zzabaabazz. Самый длинный — aba. Но есть еще и zz. Или я неправильно понял?
не правильно понял. здесь есть три наидлиннейших повторяемых паттерна: zz, aba, ba. все их суффиксы также паттерны. у строки "abcabcabeabe" есть два суперпаттерна abc и abe которые имеют общий суффикс ab, чтобы не вывести в конце паттерны дважды можно например построить бор.
UPD: "abc и abe которые имеют общий ПРЕФИКС ab"
Ок, а как искать сразу длиннейшие паттерны? Как я это должен делать?
"здесь есть три наидлиннейших повторяемых паттерна: zz, aba, ba". То есть паттерн ba не считается подстрокой aba? "лучше понимать под набором паттернов наидлиннейший и все его суффиксы". Вообще не понял. У нас есть, скажем, паттерн abcdba. Его подпаттернами будут считаться только abcdb, abcd, abc, ab? А как же bcdb, cdb и прочие? И, в конце концов, объясни, каким образом ты предлагаешь всё это реализовывать?
Тут я немного ошибся, да, ba можно считать супперпаттерном если различать их по префиксам а не по всем подстрокам.
Если хочешь большей конкретики дай ссылку на задачу. Искать сразу супер паттерны по префиксам можно на суффиксном массиве. Точно алгоритм не могу описать, если дашь ссылку на задачу попробую идеи воплотить в алгоритм, а так пальцем по воде сложно да и не охото время терять. Все суффиксы с одинаковым префиксом длины k в суффиксном массиве идут последовательно (порядок любой, но между двумя строками с одинаковым суффиксом есть только такие и никакой другой быть не может). По этому подмассиву для данного префикса легко понять является ли он паттерном или нет. Вот от этих соображений отталкиваясь и нужно делать решение. Квадрат от длины строки вроде бы видится сразу.
"лучше понимать под набором паттернов наидлиннейший и все его суффиксы" блин читай "все его префиксы". Я кривой, то суффиксы то префиксы, запутался.
Мелкие паттерны не обязаны быть подстроками длиннейшего, это длинный паттерн обязан состоять из паттернов меньшей длины. Может быть паттерн длины 2, который не входит в самый длинный паттерн, но я должен вывести его в ответ. У меня была как раз обратная идея, все паттерны длины более чем 2 должны состоять исключительно из комбинаций паттернов длины 2 , но я не придумал, как собирать большие паттерны из мелких с нормальной сложностью.
Предложение "Мелкие паттерны не обязаны быть подстроками длиннейшего, это длинный паттерн обязан состоять из паттернов меньшей длины." для меня звучит как "это не бутерброд хлеб с маслом, это бутерброд масло с хлебом". Выражайся точнее. Я утверждаю что все подстроки паттерна являются паттернами. т.е. любой паттерн является либо максимальным, либо есть другой более длинный паттерн содержащий его как подстроку. При это я нигде не сказал что максимальный паттерн один. или что не может быть нескольких максимальных паттернов с разными длинами. пример. Соответственно любой паттерн является подстрокой некоторого максимального.
PS: я щас начал называть максимальным то что раньше называл наидлинниейшим, видимо это название "наидлинниейший" и внесло путаницу, имеется ввиду максимальный по включению. т.е. нет других паттернов содержащих его как подстроку.
Согласен. Но как я должен искать максимальные паттерны, минуя этап поиска более мелких? Если я могу найти сразу максимальные паттерны, то найти все их различные подстроки не проблема. Другое дело, я не понимаю как это сделать, я вижу только обратный способ — найти наименьшие паттерны, а из них "клеить" более крупные.
PS. Возможно, я выразился некорректно. Раз уж мы начали говорить о хлебе с маслом, то бутерброд — это когда масло намазывается на хлеб, а не когда хлеб намазывается на масло. Я могу найти паттерны длины 2, путем их объединения (если оно возможно), получить все паттерны длины 3, 4 и так далее. Таким образом я получу все максимальные по включению паттерны и все их подстроки. Однако, мне непонятно как я могу СРАЗУ найти максимальные паттерны (причем еще и гарантировать их максимальность), чтобы затем разбить их на более мелкие паттерны.
Еще момент: "для простоты подсчета лучше понимать под набором паттернов наидлиннейший и все его СУФФИКСЫ", "я щас начал называть максимальным то что раньше называл наидлинниейшим, видимо это название "наидлинниейший" и внесло путаницу, имеется ввиду максимальный по включению. т.е. нет других паттернов содержащих его как ПОДСТРОКУ". Не чувствуешь противоречия? Так имеется в виду подстрока или суффикс?
"Так имеется в виду подстрока или суффикс?" имеется в виду префикс :) я выше сделал апдейты. Вообще рассуждения про подстроку верны. Поэтому они верны и для суффикса и для префикса. Но чтобы проще искать такие фиговины я предложил разбить множество подстрок на те, у которых один из концов совпадает. Вообще лучше первый конец, тогда речь идёт о префиксах и суффиксном массиве. Если второй конец, то суффиксы и префиксный массив.
Мне кажется, тут суффиксный автомат будет действительно в тему... Например, так. Склеиваем все строки массива используя разделители. Перебираем все подстроки наименьшей из них. По склейке строим автомат. Находим позиции всех вхождений подстроки. Считаем количество тех отрезков между разделителями, где более одного вхождения. Если процент подходит — добавляем в ответ. Асимптотику вот так сразу не могу оценить, но это вроде должно работать быстрее...
Не уверен. Сначала мы строим автомат за O(m*t), потом делаем t^2 запросов поиска количества вхождений, длина искомой подстроки, в худшем случае, t/2, то есть время одного запроса — O(t). Имеем сложность O(n*(m*t+t^3))=O(n*t^3). Сложность моего алгоритма была O(n*m*t^2*log(t)), учитывая, что t<=400, a m<=20, t>m*log(t), значит O(n*t^3)>O(n*m*t^2*log(t)). Возможно, конечно, у решения с суффиксным автоматом будет намного лучшая константа, но даже это не решит моих проблем, мне нужна лучшая асимптотика.
Придумал довольно простое решение с бором.
Для каждой строки добавляем все её суффиксы в бор при этом в каждой вершине запоминаем длину пути от корня, а также минимум и максимум позиции начала этого суффикса. Затем (или по ходу) отмечаем те вершины, которые являются паттернами, исходя из условия Max — Min >= Len. Удаляем все вершины не являющиеся паттернами. Объединяем полученные боры для всех m строк попутно считая в какое количество строк входит каждая вершина. Удаляем из бора те вершины что нам не подходят. Обходим бор выводя текущую строку в каждой вершине.
Сложность решения t^2 * m * n.
Понятно, что бор построенный для каждой вершины можно сжать в суффиксный автомат т.е. сократить потребление памяти до O(t). Тупо построить его как суффиксный автомат за O(t) я не знаю как, потому как не понимаю как обновлять минимумы и максимумы. Но я плохо разбираюсь в суффиксных автоматах. Полагаю что вот этот сжатый до автомата бор можно построить быстрее чем за квадрат.
Ну как бы сжатый бор по суффиксам — это уже суффиксное дерево будет.
Ну есть идея (для одного массива, а для всех решать поотдельности же?): для каждой строки постороить суффиксный автомат, и искать паттерны дфс-ом по состояниям автоматов, и вылетать когда строчка не будет подстрокой >X% строк. Будет время примерно O(Answer) для каждого массива строк.
ДФС по состояниям автоматов ДЛЯ КАЖДОЙ СТРОКИ — это как минимум O(суммы длин строк массива), разве нет? Поясните, что имеете в виду.
На счет асимптотики не уверен, но все же быстрее решения описанного вами.
О'кай, я же не против =) А как все-таки искать паттерны по этим автоматам?
Будем хранить для каждой строки позицию в автомате на которой мы сейчас находимся, если нет перехода — считаем, что в той строке такого паттерна нет. Если в какой-то момент стало меньше Х% строк, в которых еще есть паттерн — дальше искать нет смысла. В каждом состоянии в которое мы зашли окончился какой-нибудь паттерн.
Минус этого решения — нужно много памяти.