Я читаю о массивах LCP и их использовании в сочетании с массивами суффиксов при решении проблемы «Самая длинная общая подстрока». В этом видео говорится, что часовые, используемые для разделения отдельных строк, должны быть уникальными, а не...

Из раздела 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 =...

Я работаю над программой для поиска самой длинной общей подстроки между несколькими строками. Я снизил свой подход до использования массива суффиксов или дерева суффиксов. Я хочу посмотреть, какой подход лучше (если он есть) и почему. Также для...

Я пытаюсь понять реализацию алгоритма создания массива суффиксов линейного времени Карккайненом, П. Сандерсом. Подробности алгоритма можно найти здесь . Мне удалось понять общую концепцию, но я не смог сопоставить ее с предоставленной реализацией...

Знание внутренних узлов полезно в дереве суффиксов, поскольку они могут помочь вам решить такие проблемы, как поиск самой длинной повторяющейся подстроки. Их трудно построить на месте (вспомните интервью на доске). Поэтому люди посоветовали мне...

Я нашел реализацию массива суффиксов в Ruby и немного изменил ее. Вот что у меня есть: class SuffixArray def initialize(str) @string = str @suffix_array = [] (0...str.length).each do |i| substring =...

Я просто хочу знать, когда дерево суффиксов превосходит расширенный массив суффиксов. После прочтения Замена суффиксных деревьев расширенными суффиксными массивами я не вижу причин использовать суффиксные деревья больше. Некоторые методы могут...

Рассмотрим строку длины n (1 ‹= n ‹= 100000). Определите его минимальный лексикографический оборот. Например, обороты строки «алабала»: alabala labalaa abalaal balaala alaalab laalaba aalabal and the smallest among them is “aalabal”....

Как вычислить массив LCP для массива суффиксов? Он не должен быть самым эффективным. O(n log n) или O(n) подойдет. Что-то относительно легко закодировать, если это возможно.

Может кто-нибудь объяснить, как работает этот код для построения LCP из массива суффиксов? suffixArr[] — это массив, в котором suffixArr[i] содержит значение индекса в строке для суффикса с рангом i . void LCPconstruct() { int...

Предисловие: Мой вопрос в основном связан с алгоритмами, поэтому, даже если вы не знакомы с суффиксами и массивами LCP, вы, вероятно, сможете мне помочь. В этой статье описывается, как эффективно использовать массивы суффиксов и LCP для...

Имея строку S , я хочу вычислить количество подстрок, которые встречаются n раз (1 ‹= n ‹= s.length()). Я сделал это с помощью катящегося хэша , это можно сделать с помощью суффиксного дерева. Как это можно решить, используя массив суффиксов...

Я успешно реализовал этап BWT (используя обычную сортировку строк) для тестового стенда сжатия , который я пишу. Я могу применить BWT, а затем обратное преобразование BWT, и результат будет соответствовать входу. Теперь я хотел ускорить создание...

Алгоритмы поиска самой длинной повторяющейся подстроки сформулированы следующим образом 1)build the suffix tree 2)find the deepest internal node with at least k leaf children Но я не могу понять, почему это работает, так что в основном, что делает...

Недавно я обнаружил интересную проблему в Интернете. Краткое заявление в следующем: Обратите внимание, что общее ограничение по времени не должно быть равно 1,00 с (сложность по времени ‹ 10^8). Теперь студент А нашел строку, состоящую только...