Самая длинная повторяющаяся (k раз) подстрока

Я знаю, что это несколько запутанная тема, но я достиг предела помощи, которую я могу получить от того, что »С уже ответили.

Это дляРозалинд проект проблемы LREP, Я'я пытаюсь найти самую длинную k-peated подстроку в строке, и я 'былпредоставлена суффикс дерева, что приятно. Я знаю, что мне нужно аннотировать таблицу суффиксов числом выходов из каждого узла, а затем находить узлы с>=k потомки, и, наконец, найти самые глубокие из этих узлов. По теории яя поставил

Мы получили большую помощь от следующих ресурсов (к сожалению, я могу только опубликовать 2):

Найти самую длинную повторяющуюся последовательность в строкеПоиск в глубину (Python)

Я могу получить пути от корня до каждого листа, но я могуНе могу понять, как предварительно обработать дерево таким образом, чтобы я мог получить количество потомков от каждого узла. У меня есть отдельный алгоритм, который работает на небольших последовательностях, но этос экспоненциальной сложностью, поэтому для больших вещей это занимает слишком много времени. Я знаю, что с DFS я должен быть в состоянии выполнить всю задачу в линейной сложности. Чтобы этот алгоритм работал, мне нужно иметь возможность получить самый длинный k-торф из строки длиной ~ 40000 менее чем за 5 минут.

Вот's некоторые примеры данных (первая строка:sequence, вторая линия:kформат таблицы суффиксов:parent child location length):

CATACATAC$
2
1 2 1 1
1 7 2 1
1 14 3 3
1 17 10 1
2 3 2 4
2 6 10 1
3 4 6 5
3 5 10 1
7 8 3 3
7 11 5 1
8 9 6 5
8 10 10 1
11 12 6 5
11 13 10 1
14 15 6 5
14 16 10 1

Выход из этого должен быть.CATAC

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

#authors listed at
#http://en.literateprograms.org/Depth-first_search_(Python)?action=history&offset=20081013235803
class Vertex:
    def __init__(self, data):
        self.data = data
        self.successors = []

def depthFirstSearch(start, isGoal, result):
    if start in result:
        return False

    result.append(start)

    if isGoal(start):
        return True
    for v in start.successors:
        if depthFirstSearch(v, isGoal, result):
            return True

    # No path was found
    result.pop()
    return False

def lrep(seq,reps,tree):
    n = 2 * len(seq) - 1
    v = [Vertex(i) for i in xrange(n)]
    edges = [(int(x[0]),int(x[1])) for x in tree]
    for a, b in edges:
        v[a].successors.append(v[b])

    paths = {}
    for x in v:
        result = []
        paths[x.data] = []
        if depthFirstSearch(v[1], (lambda v: v.data == x.data), result):
            path = [u.data for u in result]
            paths[x.data] = path

Что я'Я хотел бы сделать это предварительно обработать дерево, чтобы найти узлы, которые удовлетворяютdescendants >= k Требование до нахождения глубины. У меня нетдаже не понял, как яЯ собираюсь вычислить глубину еще. Хотя я представляюУ меня будет некоторый словарь для отслеживания глубины каждого узла в пути, а затем суммы.

Итак, мой первый самый важный вопрос:Как мне предварительно обработать дерево потомками? "

Мой второй менее важный вопрос:После этого, как я могу быстро вычислить глубину? "

Постскриптум Я должен заявить, что этоне домашнее задание или что-то в этом роде. Я'Я просто биохимик, пытающийся расширить свой кругозор с помощью некоторых вычислительных задач.

 Gambrinus10 нояб. 2012 г., 20:49
Когда я смотрю больше на это, я понимаю, что ям дан список ребер а не само дерево. Поэтому мне нужно генерировать дерево из краев, в то же время аннотируя с потомками на каждом узле. Я просто нене знаю, как начать.
 Pierre14 нояб. 2012 г., 07:33
вы могли бы спроситьbiostars.org тоже.

Ответы на вопрос(1)

Решение Вопроса

Хороший вопрос для упражнения в основных строковых операциях. Я больше не помнил дерево суффиксов;) Но, как вы сказали: теоретически, вы настроены.

Как мне предварительно обработать дерево с потомками?

википедия-заглушка на эту тему немного сбивает с толку. Вам нужно только знать, если вы самый внешний неконечный узел сn >= k Дети. Если вы нашли подстроку от корневого узла к этому во всей строке, суффикс-дерево сообщит вам, что естьn возможные продолжения. Так должно бытьn места, где эта строка встречается.

После этого, как я могу быстро вычислить глубину?

Простая ключевая концепция этой и многих подобных проблем состоит в том, чтобы выполнить поиск в глубину: в каждом узле спросите дочерние элементы об их значении и верните максимальное из них родителю. Корневой узел получит конечный результат.

Как рассчитываются значения, зависит от проблемы. Здесь у вас есть три возможности для каждого узла:

Узел не имеет дочерних элементов. Это лист-узел, результат недействителен.Каждый ребенок возвращает неверный результат. Это последний нествольный узел, результат равен нулю (после этого узла больше нет символов). Если этот узел имеетn childs, появляется объединенная строка каждого ребра от корня до этого узлаn раз во всей строке. Если нам нужно хотя быk узлы иk > nрезультат также недействителен.Один или несколько листов возвращают что-то действительное. Результатом является максимум возвращаемого значенияплюс длина строки прикреплена к краю.

Конечно, вы также должны вернуть соответствующий узел. В противном случае вы узнаете, какова длина самой длинной повторяющейся подстроки, но не там, где она есть.

Код

Вы должны сначала попытаться написать это самостоятельно. Построить дерево просто, но не тривиально, если вы хотите собрать всю необходимую информацию. Тем не менее, вот простой пример. Обратите внимание: все проверки работоспособности выпадают, и все ужасно терпит неудачу, если ввод неверен. Например. не пытайтесь использовать какой-либо другой корневой индекс, кроме одного, не ссылаться на узлы как на родителя, который не былt упоминается как ребенок и т. д. Много возможностей для улучшения *намек;) *.

class Node(object):
    def __init__(self, idx):
        self.idx = idx     # not needed but nice for prints 
        self.parent = None # edge to parent or None
        self.childs = []   # list of edges

    def get_deepest(self, k = 2):
        max_value = -1
        max_node = None
        for edge in self.childs:
            r = edge.n2.get_deepest()
            if r is None: continue # leaf
            value, node = r
            value += len(edge.s)
            if value > max_value: # new best result
                max_value = value
                max_node = node
        if max_node is None:
            # we are either a leaf (no edge connected) or 
            # the last non-leaf.
            # The number of childs have to be k to be valid.
            return (0, self) if len(self.childs) == k else None
        else:
            return (max_value, max_node)

    def get_string_to_root(self):
        if self.parent is None: return "" 
        return self.parent.n1.get_string_to_root() + self.parent.s

class Edge(object):
    # creating the edge also sets the correspondending
    # values in the nodes
    def __init__(self, n1, n2, s):
        #print "Edge %d -> %d [ %s]" % (n1.idx, n2.idx, s)
        self.n1, self.n2, self.s = n1, n2, s
        n1.childs.append(self)
        n2.parent = self

nodes = {1 : Node(1)} # root-node
string = sys.stdin.readline()
k = int(sys.stdin.readline())
for line in sys.stdin:
    parent_idx, child_idx, start, length = [int(x) for x in line.split()]
    s = string[start-1:start-1+length]
    # every edge constructs a Node
    nodes[child_idx] = Node(child_idx)
    Edge(nodes[parent_idx], nodes[child_idx], s)

(depth, node) = nodes[1].get_deepest(k)
print node.get_string_to_root()

Ваш ответ на вопрос