Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [suffix-trees]

The tag has no usage guidance.

0
votes
0answers
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 ...
3
votes
1answer
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", "...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 [1] [2] seems to skip over whatever details that would make me comfortable ...
4
votes
1answer
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. ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
6
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
5
votes
1answer
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 ...
2
votes
1answer
2k views

Why does a suffix tree have a linear number of nodes (relative to input string size)?

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.
5
votes
1answer
360 views

What are the effects of the alphabet size on construct algorithms for suffix trees?

For what size alphabet does it take longer to construct a suffix tree - for a really small alphabet size (because it has to go deep into the tree) or for a large alphabet size? Or is it dependent on ...