Вопросы по теме 'suffix-tree'
Сопоставление суффикса Trie, проблема с операцией сопоставления
Я столкнулся с проблемой сопоставления суффиксов Trie, я разработал суффиксное дерево с 26-сторонним деревом для представления символов в узле и значения, связанного с каждым узлом. Значение каждого узла обозначает либо индекс, с которого строка...
92 просмотров
schedule
30.11.2021
Эффективный способ найти самую длинную повторяющуюся строку для Python (из Programming Pearls)
Из раздела 15.2 Programming Pearls
Коды C можно посмотреть здесь: http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c
Когда я реализую это на Python, используя суффикс-массив:
example = open("iliad10.txt").read()
def comlen(p, q):
i =...
5584 просмотров
schedule
24.02.2022
Учитывая строку, найти все ее перестановки, которые являются словом в словаре
Это вопрос интервью:
Дана строка, найти все ее перестановки, которые являются словом в словаре.
Мое решение:
Поместите все слова словаря в дерево суффиксов, а затем выполните поиск каждой перестановки строки в дереве.
Время...
4533 просмотров
schedule
27.02.2022
Насколько линейна временная сложность построения суффиксного дерева в наихудшем случае?
Мне трудно понять, почему временная сложность построения суффиксного дерева в наихудшем случае является линейной, особенно когда нам нужно построить суффиксное дерево для строки, которая может состоять из повторяющихся одиночных символов , таких как...
894 просмотров
schedule
07.04.2022
Дерево суффиксов против массива суффиксов для LCS
Я работаю над программой для поиска самой длинной общей подстроки между несколькими строками. Я снизил свой подход до использования массива суффиксов или дерева суффиксов. Я хочу посмотреть, какой подход лучше (если он есть) и почему. Также для...
1380 просмотров
schedule
08.04.2022
конечное состояние или суффиксное дерево
Я хочу создать алгоритм, который находит подстроки внутри строки, которая существует в алфавите. Например, в строке «abcdefhhhasddasdabbba» я хочу найти подстроки, порожденные алфавитом {'a','b'}
Итак, мой вывод будет таким: ab, a, abbba
Если я...
153 просмотров
schedule
11.06.2022
Массив суффиксов, обозначающий внутренние узлы
Знание внутренних узлов полезно в дереве суффиксов, поскольку они могут помочь вам решить такие проблемы, как поиск самой длинной повторяющейся подстроки.
Их трудно построить на месте (вспомните интервью на доске). Поэтому люди посоветовали мне...
59 просмотров
schedule
04.07.2022
Как использовать структуру данных Trie, чтобы найти сумму LCP для всех возможных подстрок?
Описание проблемы: Ссылки: Развлечение со строками
Основываясь на описании проблемы, наивный подход к нахождению суммы длин LCP для всех возможных подстрок (для данной строки) выглядит следующим образом:
#include <cstring>...
738 просмотров
schedule
01.09.2022
Ищете реализацию дерева суффиксов в C#?
Я реализовал базовый поиск исследовательского проекта. Я пытаюсь сделать поиск более эффективным, создав дерево суффиксов . Меня интересует реализация C# алгоритма Ukkonen . Я не хочу тратить время на создание собственного, если такая реализация...
13133 просмотров
schedule
19.11.2022
Поиск самой длинной общей подстроки в большом наборе данных
За последние несколько дней я тщательно изучил это, я прочитал так много вещей, что теперь я запутался еще больше, чем когда-либо. Как найти самую длинную общую подстроку в большом наборе данных? Идея состоит в том, чтобы удалить повторяющийся...
2539 просмотров
schedule
19.06.2023
Суффиксные массивы и суффиксные деревья
Я просто хочу знать, когда дерево суффиксов превосходит расширенный массив суффиксов.
После прочтения Замена суффиксных деревьев расширенными суффиксными массивами я не вижу причин использовать суффиксные деревья больше. Некоторые методы могут...
3780 просмотров
schedule
12.02.2023
Построение суффиксного дерева ACB, когда у нас уже есть суффиксное дерево AB
Недавно я столкнулся с вопросом о дереве суффиксов. Предположим, у нас уже есть суффиксное дерево для строки S=AB, т. е. S является конкатенацией префикса A и суффикса B строки S. Теперь мы хотим построить суффиксное дерево U=ACB. Каков наиболее...
52 просмотров
schedule
08.03.2023
подсчитать количество вхождений каждой подстроки?
Имея строку S , я хочу вычислить количество подстрок, которые встречаются n раз (1 ‹= n ‹= s.length()). Я сделал это с помощью катящегося хэша , это можно сделать с помощью суффиксного дерева. Как это можно решить, используя массив суффиксов...
539 просмотров
schedule
05.06.2023
Как удалить все повторяющиеся слова и буквы строки?
Я пытаюсь удалить каждый символ, повторяющийся более 2 раз, из очень длинной строки. Так, например, слово Terrrrrrific становится Terrific .
Теперь мой вопрос: как мне отфильтровать повторы, которые включают более одного символа, то есть, если...
68 просмотров
schedule
18.08.2023
Поиск всех общих непересекающихся подстрок
Учитывая две строки, я хотел бы определить все общие подстроки от самой длинной до самой короткой.
Я хочу удалить любые «подстроки». Например, любые подстроки «1234» не будут включены в соответствие между «12345» и «51234».
string1 = '51234'...
1536 просмотров
schedule
25.08.2023
Поиск всех повторяющихся подстрок в строке и частота их появления
Проблема:
Мне нужны все последовательности символов, которые соответствуют следующему:
Последовательность символов должна присутствовать более одного раза (поэтому (LE, 1) недопустимо).
Последовательность символов должна быть длиннее одного...
8095 просмотров
schedule
31.07.2023
Самая длинная максимальная повторяющаяся подстрока
Подстрока может иметь длину 1,2,3... Вопрос, который я пытался решить, заключался в поиске подстроки, которая встречается максимальное количество раз. Таким образом, в основном это сводилось к поиску персонажа с максимальной частотой. Однако я...
2181 просмотров
schedule
12.12.2022
Самая длинная повторяющаяся подстрока с правильностью не менее k вхождений
Алгоритмы поиска самой длинной повторяющейся подстроки сформулированы следующим образом
1)build the suffix tree
2)find the deepest internal node with at least k leaf children
Но я не могу понять, почему это работает, так что в основном, что делает...
835 просмотров
schedule
03.06.2023
Как получить как ключ, так и значения в suffixtree.substringdict
Я использую suffixtree для извлечения совпадающей подстроки. Файл readme содержит пример как --
>>> import SuffixTree.SubstringDict
>>> d = SubstringDict.SubstringDict()
>>> d['foobar'] = 1
>>>...
155 просмотров
schedule
16.12.2022
