Questions tagged [suffix-trees]

The tag has no usage guidance.

18 questions
6 views

Suffix-automaton Largest common substring of multiple strings

Can anyone help with understanding how to solve "Largest common substring of multiple strings" problem with usage of Suffix-automaton? I've found this a really good article about SA . But ...
85 views

Longest common substring many strings to one

I'd like to find longest common substring (occurrences, start index) between one string and many others. For example source string - "abcdefghijklmncdop" other strings - ["cd", "ghi", "mn", "zw", "...
38 views

How use generalized suffix tree to match prefix string?

I know that generalized suffix tree can match substring for a given pattern. But I have need a data structure which is able to match prefix of many strings. match sub string of of many strings. For ...
97 views

Find shortest prefix to generate original string by overlapping

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed). For ...
379 views

Longest repeated substring

I am trying to solve a problem- Longest repeated substring in a string. Firstly, I built a suffix tree that takes O(n) time and then I traversed the suffix tree to find the deepest internal node. I am ...
187 views

Understanding Martin Farach's suffix tree algorithm

I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have   seems to skip over whatever details that would make me comfortable ...
97 views

Where did Don Knuth say that suffix trees were the “Algorithm of the Year 1973?”

If you do a quick search for suffix trees on Google, you'll find a bunch of sources saying that Don Knuth called them the "Algorithm of the Year 1973." However, I can't seem to find a source on this. ...
76 views

Suffix Trie with indexes of the last substring

As I understood there is a algorithm ("black box") that build trie from a string by O(n) time complexity, This algorithm use pointer to the first appearance of the substring in the string. Is the a ...
222 views

return all strings contains given string in suffix tree

Here is my question: Given a compressed suffix tree of string S and a substring T. I need to return all substrings of S that begins with the substring T sorted by lexicographic order. My approach: I ...
203 views

Longest palindrome size with suffix trees

Suppose that I want to get the size of the biggest palindrome in a string s, and I am restricted to do it using suffix trees what is the best complexity I will get and why? I checked other answers but ...
347 views

find if a string is periodic using a suffix tree, and prove it

A string s of length n is periodic if there is a string $u$ of length <= n/2 such that $s = u^ku'$, where $k$ is ...
51 views

Substring problems in suffix trees [duplicate]

Assume that we have some efficient way of creating a suffix tree of a string. Then I'm interested in efficient ways of finding: Length of longest repeated substring. Given some string $S$, then a ...
538 views

Finding a certain prefix of a string

Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a ...
439 views

Suffix Tree algorithm complexity [closed]

I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident ...
439 views

How to create a suffix tree by hand

I will soon have to be able to draw a suffix tree of a word on an exam. I tried to understand the different algorithms available, but they seem rather complicated to do "by hand". I do not see a ...
111 views

Suffix trees - “smaller half trick”

I have been reading a paper Finding Maximal Pairs with Bounded Gap: An in there, there is a sentence (page 6 second paragraph): The “smaller-half trick” is used in several methods for finding ...
Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.