Созрел вопрос в свете предыдущего. Исходные данные:
n — число, >0
S — строка

Требуется найти в строке S такую подстроку максимально возможной длины, которая в S встречается не менее N раз.
Например:

S= "abcdxbcdfffbcd"
n = 2

Результат: подстрока "bcd". Встречается 3 раза.

По идее задачка, возникающая при разработке архиваторов и чего-то похожего, но решения на вскидку не нашел. Может кто знает куда копать ?

Ternary tree, suffix tree, suffix array.

Здравствуйте, D. Mon, Вы писали:

DM>Ternary tree, suffix tree, suffix array.

Спасибо, я примерно в этом направлении и думал.

Здравствуйте, chukichuki, Вы писали:

C>Спасибо, я примерно в этом направлении и думал.
Правильно. Задача элементарно решается с помощью suffix tree за линейное время. Самое трудное -- построить его.

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, chukichuki, Вы писали:

C>>Спасибо, я примерно в этом направлении и думал.
Mab>Правильно. Задача элементарно решается с помощью suffix tree за линейное время. Самое трудное -- построить его.

Как я понимаю в худшем случае (для строки вроде 'abcde....z') получится n суфиксных деревьев. Первое дерево будет представлять собой список a->b->c->d-> ... ->z
второе b->c->d->...->z, тертье с->d->...->z и т.д. В случае если в строке будут повторяющиеся последовательности, то число деревьев будет уменьшаться.

Здравствуйте, chukichuki, Вы писали:

C>Как я понимаю в худшем случае (для строки вроде 'abcde....z') получится n суфиксных деревьев.
В каком смысле? Каждой строке соответствует единственное суффиксное дерево. Никаких n там получиться не может. Если все символы разные, то устроено оно будет так: корень, из которого растут n дуг (каждая помечена соответствующим суффиксом).

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, chukichuki, Вы писали:

C>>Как я понимаю в худшем случае (для строки вроде 'abcde....z') получится n суфиксных деревьев.
Mab>В каком смысле? Каждой строке соответствует единственное суффиксное дерево. Никаких n там получиться не может. Если все символы разные, то устроено оно будет так: корень, из которого растут n дуг (каждая помечена соответствующим суффиксом).

Пример — пусть имеем строку 'abcadbс', в ней встречаются символы 'a','b','c','d'. Тогда возможны подстроки, начинающиеся с 'a', c 'b', c 'c' и с 'd'. Все возможные подстроки представляем в виде суфиксных деревьев.

Подстроки начинающиеся с буквы 'a'

a -> b -> c -> a -> d -> b -> c
     | -> d -> b -> c

Подстроки начинающиеся с буквы 'b'

b -> c -> a -> d -> b -> c
  
Подстроки начинающиеся с буквы 'c'

c -> a -> d -> b -> c

Подстроки начинающиеся с буквы 'd' 

d -> b -> c

Ощибся

Подстроки начинающиеся с буквы 'a'

a -> b -> c -> a -> d -> b -> c
| -> d -> b -> c

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, chukichuki, Вы писали:

C>>Как я понимаю в худшем случае (для строки вроде 'abcde....z') получится n суфиксных деревьев.
Mab>В каком смысле? Каждой строке соответствует единственное суффиксное дерево. Никаких n там получиться не может. Если все символы разные, то устроено оно будет так: корень, из которого растут n дуг (каждая помечена соответствующим суффиксом).

Перепутал с префиксным деревом