конечное состояние или суффиксное дерево

Я хочу создать алгоритм, который находит подстроки внутри строки, которая существует в алфавите. Например, в строке «abcdefhhhasddasdabbba» я хочу найти подстроки, порожденные алфавитом {'a','b'}

Итак, мой вывод будет таким: ab, a, abbba

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

Если я использую дерево суффиксов, то как я могу найти подстроки, которые могут не быть префиксом или постфиксом внутри дерева? Должен ли я использовать для каждого узла массив, в котором хранятся данные для поддерева, а затем проверять, содержит ли массив символы, не включенные в алфавит?

Редактировать:

Сложность имеет решающее значение.


computer-science finite-automata suffix-tree
person bill    schedule 24.05.2014    source источник
comment
Решение этой проблемы с конечным числом состояний требует всего два состояния: одно для {a,b} и одно для остального алфавита.   -  person Fred Foo    schedule 24.05.2014
comment
Я думаю, не потому, что если у него всего 2 состояния, то на выходе будет a,b,a,b...   -  person bill    schedule 24.05.2014

Ответы (1)


arrow_upward
2
arrow_downward

Это можно сделать с помощью тривиального цикла, никаких структур данных не требуется.

for each letter in word
  if letter in alphabet, then add it to a current "X"
  otherwise emit current "X" and set "X" to empty string

пример питона

word = 'aababadadadab'
alphabet = { 'a', 'b' }

X = ''
for letter in word + '$': 
  if letter in alphabet:
    X += letter
  else:
    print X
    X = ''

вывод:

aababa
a
a
ab

Я использую «$» в качестве специального символа вне алфавита для упрощения кода.

person lejlot    schedule 24.05.2014
comment
извините за недостающую информацию, но я хочу сделать это с наименьшей сложностью. Если я проверю каждую букву ввода с каждым символом в алфавите, тогда сложность будет равна O(n*m), n:len(input), m:len(алфавит) - person bill; 24.05.2014
comment
Вы неправы. проверка буквы — O(1) с использованием набора хэшей, поэтому алгоритм — O(n), самый быстрый из возможных. - person lejlot; 24.05.2014
comment
С фиксированным алфавитом вы также можете использовать битовый вектор вместо хеш-таблицы. - person Fred Foo; 24.05.2014
comment
@larsmans, но вам все еще нужно сопоставление входных символов с позициями битового вектора, что потребует хеширования (для доступа O (1)). Так в чем же разница? - person lejlot; 24.05.2014
comment
@lejlot Вам не нужно ничего хэшировать, просто используйте код символа в качестве индекса. (Это нецелесообразно для полного Unicode, но для меньших алфавитов это быстрее и проще.) - person Fred Foo; 24.05.2014
comment
Это точно так же, как использование хеш-таблицы с хешированием идентификаторов и размером максимального кода :) - person lejlot; 24.05.2014