Блог пользователя adamant

Автор adamant, история, 10 лет назад, По-английски

Hi everyone!

As you may know, it is possible to build a suffix automaton for a set of strings as well as suffix tree consisting of all suffixes of strings from the set. Question is as follows: for each string Sk consider set Vk of vertices/states of tree/automaton that corresponds to the substrings of Sk. Is it true that ? Can you prove it or make a counter-example?

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What prevents |Vk| from being always Θ(|Sk|) for suffix trees?