поиск подстроки из строки

Question

Ввод: строка S = AAGATATGATAGGAT.

Вывод: Максимальные повторы, такие как GATA (как в позициях 3 и 8), GAT (как в позициях 3, 8 и 13) и так далее ...

• Максимальное повторение - это подстрока t, встречающаяся k> 1 раз в S, и если t растянута влево или вправо, это произойдет менее чем в k раз.

• Листовые потомки внутреннего узла - это суффиксы, каждый из которых имеет левый символ.

• Если левые символы всех потомков листьев не все идентичны, это называется «левосторонним» узлом.

• Максимальное количество повторяющихся левых разнесенных внутренних узлов.

Общая идея:

• Построить дерево суффиксов, а затем выполнить DFS (поиск в глубину) на дереве

• Для каждого листа пометьте его левым символом

• Для каждого внутреннего узла:

• Если хотя бы один ребенок помечен *, то пометьте его *

• В противном случае, если ярлыки его детей разнообразны, пометьте их *.

• В противном случае все дочерние элементы имеют одинаковую метку, скопируйте ее в текущий узел

Правильна ли приведенная выше идея? Каким должен быть псевдокод? Тогда я могу попытаться написать программирование самостоятельно.

Answer 1

Ваша идея хороша, но с деревом суффиксов вы можете сделать что-то еще проще.

Пусть T будет деревом суффиксов вашей последовательности.

Пусть x - узел в T, T_x - поддерево T с корнем x.

Пусть N_x - номер листа в T_x

Пусть слово (x)быть словом, созданным путем обхода T от корня к узлу x

Теперь, используя определение дерева суффиксов, получаем:

Количество повторений слова (x) = N_x иположение этих слов - метка каждого листа

Алгоритм для этого будет базовым обходом дерева, для каждого узла в дереве вычисляется N_x, если N_x> 2, добавьте это к вашемурезультат (если вам нужна позиция, вы можете добавить метку каждого листа)

Псевдокод:

ввод:

mySequence

вывод:

Результат (список слов, которые повторяются с количеством и положением)

Алгоритм:

T = суффиксTree (mySequence)

Для каждого внутреннего узла X в T:

  T_X = subTree(T)
  N_X = Number of lead (T_X)
  if N_X >=2 :
  Result .add ( [word(X), N_X , list(label of leafs)] )

return Результат

Пример:

давайте возьмем пример википедии для суффиксных деревьев: "BANANA" :

мы получаем:

N_A = 3 so "A" repeats 3 times in position {1,3,5}
N_N=2  so "N" repeats 2 times  in position {2,4}
N_NA=2  so "NA" repeats 2 times in position {2,4}

---

Я нашел этот документ, который, кажется, рассматривает вашу проблему так же, как вы, так что да, я думаю, что ваш метод - написать:

Написание приблизительных повторяющихся или общих мотивов с использованием дерева суффиксов

Извлечение

Мы представляем в этой статье два алгоритма.Первый извлекает повторяющиеся мотивы из последовательности, определенной над алфавитом сигма.Например, сигма может быть равна {A, C, G, T}, и последовательность представляет кодирование макромолекулы ДНК.Найденные мотивы соответствуют словам в одном и том же алфавите, которые встречаются в последовательности как минимум несколько раз q раз, причем не более e несовпадений каждый раз (q называется ограничением кворума). [...]

Вы можете скачать его и посмотреть на него, автор дает псевдокод для вашего алгоритма.

Надеюсь, это поможет