Comments 35
Последняя фраза улыбнула. Годнота, лайк. На собеседовании спрашивают совсем азы, материал избыточный, но хороший.
Поиск уже известных подстрок в строке - это хорошо. А может кто-нибудь подсказать, как в строке найти все повторяющиеся подстроки, которые заранее неизвестны?
Например, я нашел реализацию алгоритма поиска тандемных повторов - т.е. когда повторяющиеся подстроки следуют друг за другом.
А как найти все повторяющиеся хотя бы по 2 раза подстроки, произвольно разбросанные по строке?
Суффиксное дерево. Любая повторяющаяся подстрока соответствует вершине в дереве, у которой есть несколько листьев в поддереве. Единственная проблема - пересечение нескольких вхождений. Если пересечения запрещены, то надо считать в поддереве самый левый и самый правый листья (по положение в строке). И в каждой вершине смотреть, достаточно ли далеко они отстоят, чтобы пересечения не было. Аккуратно обрабатывайте виртуальные вершины на ребрах: это все делается за константу - вы зная положения левого и правого листьев знаете максимальную разрешенную глубину вершины. Вот и смотрите, какая часть ребра сюда подходит.
Алгоритм Укконена позволит решить всю задачу за O(n). Поищите - на хабре были хорошие статьи.
Вот как раз насчёт пересечений вопрос. Допустим, есть строка 12341234
Алгоритм Укконена находит не только подстроку 1234, но и 123, 12 и 1. Как сделать так, чтобы алгоритм находил только 1234?
Надо идти вниз до упора. Т.е. текущая вершина подходит, если все ее дети имеют только по одному листу (и детей больше одного), или ее глубина равна разнице между левым и правым вхождением.
Глубина - это уровень, на котором вершина находится? А что такое левое и правое вхождение?
В строке "ababa" подстрока "aba" встречается два раза, но эти два вхождения пересекаются между собой. Неясно, критично ли это вам, но часто такие вхождения не считают за два. В суффиксном дереве же у вершины соответствующей строке "aba" в поддереве будет два листа, т.ч. надо как-то отдельно бороться с такими близкими вхождениями.
Во-первых, можно для каждой подстроки искать только самое левое и самое правое вхождения. Если они отстоят друг от друга хотя бы на длину подстроки, то вот эта подстрока вам подходит. Вспомните, что в суффиксном дереве каждый лист соответствует одному суффиксу строки (при условии, что в в конец строки какой-нибдь уникальный '$' добавили). Каждая подстрока соответствует вершине в дереве, а все ее вхождения - листьям в поддереве. Обычно все листья помечают индексом начала суффикса. Тогда для каждой подстроки, она же вершина в дереве, все вхождения - это набор пометок на листьях в поддеревьях. Поскольку нам интересны только левое и правое входения подстроки, то можно написать рекурсивную функцию, которая возвращает минимальную и максимальную пометку в поддереве. Если их разность не меньше длины подстроки (она же длина пути от корня до вершины, она же глубина в дереве), то вот эту подстроку-вершину можно выдать в ответ.
Чтобы не выдавать в ответ подстроки являющееся подстроками других, нужно сделать две вещи: Во-первых, жадно расширять подстроку в ответе вправо как можно дальше. Для этого в ответ должна подходить только вершина, ниже которой по дереву хороших вершин нет. Т.е. в каждом ее ребенке разность максимальной и минимальной пометок меньше глубины ребенка. Во-вторых, вам надо будет отдельно обработать те подстроки, которые являются суффиксами других подстрок в ответе. Вроде как для "abcabc" алгоритм выше выдаст "abc", "bc", "c". Для этого строки надо отсортировать по началу (подсчетом. В каждой позиции может начаться только одна строка). Потом пройтись слева-направо помня максимально правый конец. Если текущая строка не торчит правее этого конца, то она внутри какой-то одной сторки, ее надо выкинуть. Если торчит, то ее выдать в ответ и увеличить правый конец.
Еще надо помнить, что алгоритм Укконена выдает сжатое дервево, где все вершины с одним ребенком выкинуты, а на ребрах написаны целые строки. Тут вам надо обработать случай, что в ответ надо выдать виртуальную вершину на ребре к отцу. Ну это возникает только тогда, когда для отца разница макс и мин пометок больше его глубины, а для текущей венршины - меньше. Тогда есть какая-то вершина на ребре, глубина которой равна вот этой разности. Ее и надо выдать в ответ.
Еще совет, чтобы не мучатся с проверками, а подходит ли текущая вершина, или можно опуститься ниже, пусть ваша рекурсивная функция возвращает не только мин и макс пометку, но и есть ли "хорошая" вершина вот в том поддереве (включая ребро к отцу). Тогда проверка упрощается - если ни один рекурсивный вызов не вернул истину, вот тогда текущая вершина может быть хорошей. Иначе - даже проверять глубину не надо. Только не выходите из функции сразу же - не забудьте, что какие-то другие дети текущей вершины все еще могут попасть в ответ, даже если первый ребенок что-то у себя нашел.
А про пересечения имелось ввиду что-то вроде "ababa" - тут два вхождения "aba" пересекаются между собой. Если это плохо, то как раз нужно левое/правое вхождение, которые будут остоять на 2 символа друг от друга, что меньше глубины 3. Вот для "ab" расстояние будет такм же 2 и уже не превзойдет глубину.
И вообще, вам стоит немного подумать над формализацией задачи. Например, в "123434123" есть повторяющиеся более одного раза строки "123" и "34". Но их вхождения пересекаются. Они вам подходят? Если нет, то какую из двух брать? Если да, то почему тогда не подходит строка "23"?
Над формализацией подумаю. Скажем так, не подходят строки, вложенные в более длинные. Если какая-то длинная подстрока повторилась более одного раза, её подстроки уже не нужны. Хотя понятно, что они тоже повторились.
Что-то вообще у меня странности с этим алгоритмом. Вот есть у меня строка: 123123. Прекрасно, находит подстроку 123. То, что при этом находит еще 23 - пока что бог с ним.
Теперь прогоняем его на строке 01231234. Алгоритм находит не только 123 и 23, но и 1234. Повторюсь: мне нужно найти только повторяющиеся более одного раза подстроки. 1234 - суффикс, который встретился только один раз. Как его отсеять?
Далее прогоняю его по строке 012341234912. И теперь алгоритм подстроку 1234 вообще не находит, хотя она повторяется дважды. Получается, что всё-таки это не тот алгоритм, который мне нужен?
Что-то вы напутали в реализации. Для строки "01231234" дерево вот такое (не художник, извините):
Тут в конце добавлен "$", как в алгорпиитме, а красным обведены вершины, которые имеют в поддереве более одного листа. Строка "1234", как вы видите, соответствует вершине ниже красной зоны - так что ее алгоритм вывести вообще никак не может. Если выводить вершины снизу вверх то там получаются "123", "23", "3". Дальше надо будет, как я писал раньше, отфильровать из них покрытые другими строками и останется только "123".
Реализация не моя, пробовал две разных. Попробовал добавить $ в конце. Действительно, для строки "01231234" выдает подстроку 1234$ - ее можно отсеять по наличию символа $.
А вот со строкой "012341234912" добавление символа $ не помогает - подстроку "1234" в узлах не выдает. Вот полное дерево:
+
+-- 012341234912$
+-+ 12
| +-+ 34
| | +-- 1234912$
| | +-- 912$
| +-- $
+-+ 2
| +-+ 34
| | +-- 1234912$
| | +-- 912$
| +-- $
+-+ 34
| +-- 1234912$
| +-- 912$
+-+ 4
| +-- 1234912$
| +-- 912$
+-- 912$
+-- $А вот со строкой "012341234912" добавление символа $ не помогает - подстроку "1234" в узлах не выдает. Вот полное дерево:
Почему не выдает-то? Вот же там узел для строки "1234":
+-+ 12
| +-+ 34 <---- вот он!
| | +-- 1234912$
| | +-- 912$У него 2 ребенка - а значит более 1 листа в поддереве. Глубина вершины 4. два вхождения в поддеревьях соответствуют суффиксам начинающимся в позициях 1 и 5 (считая с 0). Разница между минмальным и максимальным - 5-1=4 не меньше глубины. Почему не выводите-то? Может, вы при подсчете глубины забываете, что дерево сжатое? К вершине ведут 2 ребра но с символвами "12" и "34" - глубина должна быть 4, а не 2.
Действительно, для строки "01231234" выдает подстроку 1234$ - ее можно отсеять по наличию символа $.
Не должно выдвать. Вершина для строки, в конце которой $ - это лист. У него в поддереве не может быть несколько листов никак.
Какие-то проблемы у вас с реализацией алгоритма по уже готовому дереву.
Почему не выводите-то?
Потому что не могу понять, как правильно построить алгоритм вывода по уже готовому дереву.
У него 2 ребенка - а значит более 1 листа в поддереве
Слова понятны, но не понимаю, как из этого понять, что по этому узлу дерева нужно из двух строк "12" и "34" собрать одну "1234".
проблемы у вас с реализацией алгоритма по уже готовому дереву
Именно. Попробую еще раз сформулировать, что мне нужно: как из полученного суффиксного дерева извлечь полные подстроки, повторяющиеся в исходном тексте более одного раза? Бог с ним пока что, что часть из них вложены в другие. Их можно на следующем шаге отсеять.
У вас на ребрах в дереве же написаны не строки, а индексы подстроки в исходной строке, правда? Ну это важно только для очень быстрой реализации.
И дальше я работаю с идеей, что у вас алгоритм Укконена выдал сжатое дерево, где на ребрах целые строки написаны, а все вершины или листья, или разветвления.
Рекурсивная функция принимает вершину дерева v, число-глубину d и строку s, длину строки на последнем ребре l (можно как начало-длина подстроки, можно саму строку). Возвращает 3 числа: самый левый лист в поддереве,самый правый лист в поддереве, найден ли ответ в поддереве (можно bool).
Если вершина без детей, то возвращайте {n-d, n-d, 0} (n - длина исходной строки включая $).
Иначе, у нее более 1 ребенка. Рекурсивно запустились от всех детей. Передав туда (вершина-ребенок v, d + длина строки на ребре к ребенку, s + строка на ребре к ребенку, длина строки на ребре к ребенку). Из всех левых листов от рекурсивных результатов выберите минимум, из всех правых - максимум. Третье число из результатов аггрегируйте через логическое ИЛИ.
Если ни одно поддерево ответа не нашло, разница правого и левого вхождений
больше равна d-l+1, то добавляете в ответ строку s, урезанную до длины min(d, разность правого и левого вхождений).
Возвращайте {минимальный из левых листьев, максимальный из правых, нашелся ли ответ рекурсивно или в этой функции}.
Как-то так:
Compute(Node v, int d, string s, int l) -> {int, int , bool}
if нет детей у v
return {n-d, n-d, false}
left = n
right = 0
found = false
for e : ребро из v к ребенку
res = Compute(e.end, d+e.length, s + e.string, e.length)
left = max(left, res[0])
right = min(right, res[1])
found |= found
if !found and right-left >= d-l+1
found = true
s.resize(min(d-l+1, right-left))
Output(s)
return {left, right, found}
Чтобы это работало действительно быстро надо передавать не строку s, а ее позиции в исходной строке в виде начало-длина. Алгоритм Укконена так и работает уже и на ребрах написаны индексы подстрок.
Спасибо! Буду пробовать.
Еще раз, основные идеи:
подстрока повторяется - в поддереве соответствующей ей вершины (эта строка читается от корня до вершины) есть несоколько листьев.
Вхождения не персекаются, если самый левый и правый лист отстоят хотя бы на длину подстроки.
Если рассмотреть все такие вершины, то они образуют "обрубок" исходного дерева (если вершина "хорошая", то ее отец - тоже. Если строка "1234" повторяется без самопересечений, то так же и ее подстрока "123")
Для быстрой реализации вам надо в каждой вершине знать, есть ли хорошая где-то внизу (тогда эту можно не выводить) и мнимальный и максимальный лист в поддереве. Эту информацию мы возвращаем рекурсивно. А дальше немного аккуратных рассуждений, чтобы найти, где находится граница "обрубка" на ребре от отца к ребенку.
for e : ребро из v к ребенку res = Compute(e.end, d+e.length, s + e.string, e.length)
Простите, туплю: что значит "ребро из v к ребенку"?
Ну вот вы вызывались от вершины v. Из нее есть какие-то ребра к детям. Как вот тут у вершины для строки 1234 есть 2 ребенка с ребрами "1234912$" и "912$":
+-+ 12
| +-+ 34 <---- вот он!
| | +-- 1234912$
| | +-- 912$Вот е и должно перебрать 2 ребра, концы вот в те 2 вершины в дереве, со строками "1234912$" и "912$". e.end - это вершина ребенок, е.length - длина строки, e.string - сама строка ("1234912$" или "912$" соотвественно).
Это надо знать, в каком формате у вас дерево записано, чтобы понять, как их перебрать.
В одной из реализаций дерево состоит из списка вершин:
struct SuffixTree {
std::vector<Node> nodes;
...
};Каждая вершина - такая структура:
struct Node {
std::string sub = ""; // a substring of the input string
std::vector<int> ch; // vector of child nodes
size_t nstart = 0; // index of start of substring in source string
}В каждом узле - подстрока этого узла sub, nstart - индекс в исходной полной строке, с которого эта подстрока начинается, и список детей - попросту индексы узлов в полном дереве nodes. Взял отсюда (и немного дополнил - добавил запоминание индекса начала подстроки в полной строке).
Вроде что-то получилось. В алгоритме выше, наверное, должно быть:
left = min(left, res[0])
right = max(right, res[1])И вот этот кусок не совсем понятен:
if !found and right-left >= d-l+1
found = true
s.resize(min(d-l+1, right-left))Если убрать s.resize(...), то алгоритм выдает подстроки 1234, 234, 34, 4. А если не убирать, то обрезает их - выдает 123, 23, 3, 4.
Попробовал на других вариантах - такое ощущение, что не надо строку s обрезать - надо ее и выводить, если found = true.
while fnode is not None and key not in fnode.goto:
Кому-то определённо не хватает линтеров, чтобы перестать писать подобную дичь. Должно быть
while fnode and (key in fnode.goto): ...Есть ещё кучка аналогичных мест.
Здравствуйте. Цикл - это не петля и не ребро. Цикл определяется через путь. У вершин нет связности, есть степень. Связность, компоненты связности есть у неор. графов, это обязательно нужно определить! но вы это не определили. Дерево - связный граф без циклов. Ваше второе определение дерева неправильное. Если в неор. графе |V|=n и |E|=n-1, то этот граф - дерево, циклов там быть не может. Далее, вы пишете "простой цикл". Во-первых, вы его не определили, во-вторых, он не так прост. Поскольку терминология в теории графов неустоявшаяся, в одних книгах простой - без повторяющихся ребер, в других простой- без повторяющихся вершин.
Раскраска графа (не планарного) в минимальное число цветов - классическая NP-полная задача. Точный алгоритм раскраски - переборный, например, алгоритм с возвратом, для |V|<= 20 гарантированно уложимся в реальное время. Для средней и большой размерности применяются различные приближенные и эвристические алгоритмы, не дающие оптимальное решение.
Чё так сложно-то? Нам на инфоцыганских курсах сказали "за полгода до мидла", какие ещё Ахо-Корасики?
Поиск в глубину. В описании алгоритма есть вершины и "ноды'. Машинный перевод nodes? Это те же самые узлы-вершины.
Для Ф.-Б. и Флойда нет корректной постановки задачи. Ну задайте себе вопрос: для каких неориентированных графов можно воспользоваться этими алгоритмами: Дейкстрой, Ф.-Б., Флойдом?
Ну и нет алгоритма восстановления кратчайшего пути по вектору или матрице кратчайших расстояний, который был обещан. Сразу скажу, что в большинстве учебников предлагаемая там процедура восстановления кр.пути зацикливается, если попадает в цикл нулевой стоимости. Т.е. эту процедуру нужно писать самому))
Интересная статья, интересно читать)
Ещё раз, ОГРОМЕННОЕ СПАСИБО!
Любопытно, что начало статьи, как раз таки основано на заблуждениеи, которое гуляет в интернете, мол ИИ не заменит алгоритмы.
Но ведь все с точностью наоборот - ИИ в первую же очередь заменит именно составление алгоритмов)
По сути, это же и есть изобретение того самого калькулятора, только уровнем выше.
Зачем разработчику держать в памяти столько информации, когда он может обратиться к ИИ (в перспективе конечно же) и в секунду получить лучший вариант, для своей конкретной ситуации.
Это конечно не отменяет интересности данных задач, для развития собственного серого вещества.
Чтобы составить алгоритмы - думать надо. Текущий ИИ думать не умеет. Если спросить какую-нибудь очень баянистую задачку с литкода, решение которой по все формумам растиражировано, то оно выдает увиденный ранее результат. Но стоит чуть-чуть перефразировать и оно выдает полный бред. Если формо-шлепство и прочий broilerplate код оно может выдавать в промышленных масштабах, то вот с алгоритмами там все очень плохо.
Все верно, ведь речь идёт не про сейчас, а про ближайшее будущее.
Алгоритмы - это первое что заберёт на себя ИИ. А вот посторонние больших рабочих и мало того, поддерживаемых структур - до этого точно долго.
Это как картинка генеририть сейчас, по отдельности - задачки решаемы, а вот сделать из этого что-то единое - не представляется возможным.
А вот размер и сложность трёх самых отдельных задач - будет возрастать. Рано или поздно ИИ доберётся и до подобных алгоритмов.
Шпаргалка для алгособеса 2 — графовые и строковые алгоритмы