Questions tagged [suffix-trees]
The suffix-trees tag has no usage guidance.
28 questions
0
votes
1
answer
37
views
Construction time complexity of suffix automata
I was reading about suffix automata on cp-algorithms. I didn't completely understand their argument that redirecting transitions will take linear time in total. I only understood the first part, where ...
1
vote
0
answers
100
views
Efficient generalized suffix array/tree construction for prefix trees
Is there any algorithm that can efficiently construct a generalized suffix tree or array (or something similar) for a set of strings represented by a prefix tree (trie)?
In particular, I'm wondering:
...
- 1,177
3
votes
1
answer
71
views
What is the time complexity of determining maximal overlaps between bitmap images?
Given two bitmap images (two arbitrarily sized two-dimensional matrices of integer values ranging from 0 to some maximum number), I want to determine their maximum overlaps.
An overlap is a relative ...
- 5,941
2
votes
1
answer
225
views
Find repeated patterns in a string via lossy compression
Description
The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the ...
- 123
0
votes
0
answers
150
views
How to find the LCP of string pairs in a set
I have a set of $k$ strings of $n$ length each. I need an algorithmic strategy that finds the LCP (Longest Common Prefix) of each set's string pair. In addition, I need time complexity $O(k*n+a)$, ...
- 113
1
vote
1
answer
50
views
Checking the existence of a pattern in a given prefix
I need to design an algorithm that given a string $T$ of length $n$, performs $O(n)$ preprocessing, and can then answer queries of the sort "does a string $P$ of length $m$ appear in $T$ before ...
- 113
1
vote
0
answers
81
views
Why is converting a suffix tree to a suffix array not O(nklogk) time
Let's say that we have computed a suffix tree in O(n) time, and wish to use this to create a suffix array. According to wikipedia:
A suffix tree can be built in $O(n)$ and can be converted into a ...
- 143
1
vote
1
answer
135
views
How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n]
I was asked this question today:
given a very long string x, which contains only lower case alphabets. A valid substring can only started with [a, b, c, d, e] and ends with [h, i, j, k, l, n]
IF we ...
- 141
1
vote
1
answer
226
views
Efficient insertion of deterministic acyclic finite state automaton (DAFSA) into a full-text search index?
I have a problem where I can easily construct a set of deterministic acyclic finite state automata (DAFSA) and I need a full-text search index, e.g. a suffix tree/array, over all the words encoded by ...
- 111
0
votes
1
answer
69
views
Building Suffix Array from Suffix Tree. Inorder visit when node has more than two children
From the notes:
It is not difficult to observe that the suffix array $\texttt{SA}$ of
the text $\texttt{T}$ can be obtained from its suffix tree
$\texttt{ST}$ by performing an in-order visit: each ...
- 281
1
vote
0
answers
61
views
Termination Character in Suffix Trees
I am trying to create a generalised suffix tree from a very large number of strings using Ukkonen's algorithm, however I run out of unique symbols to use as string termination characters.
I was ...
- 41
3
votes
0
answers
44
views
Constructing Generalised Suffix Tree from a large set of strings
Is there a published method to construct a generalised suffix tree from a large set of strings (~ 500 000) without the need of concatenating them?
I would like to use the resulting suffix tree for a ...
- 41
3
votes
3
answers
617
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", "...
- 31
0
votes
0
answers
159
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 ...
- 123
3
votes
1
answer
258
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 ...
- 31
1
vote
1
answer
1k
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 ...
- 481
6
votes
1
answer
1k
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 ...
- 61
4
votes
1
answer
212
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.
...
- 9,222
1
vote
1
answer
451
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 ...
- 135
0
votes
0
answers
358
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 ...
- 13
0
votes
1
answer
1k
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 ...
- 369
1
vote
0
answers
79
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 ...
- 219
6
votes
1
answer
700
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 ...
- 495
0
votes
1
answer
693
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
1
answer
637
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 ...
- 203
5
votes
1
answer
133
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 ...
- 337
3
votes
1
answer
3k
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.
6
votes
1
answer
573
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 ...
- 61