Questions tagged [suffix-array]
The suffix-array tag has no summary.
21 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
1
answer
21
views
Optimal in-place suffix sorting algorithm on read-only general alphabets produces wrong results
I am trying to implement the Optimal In-Place Suffix Sorting algorithm (Section 5.5 of "Optimal In-Place Suffix Sorting" by Bingmann, Fischer, and Kurpicz, 2019), specifically the read-only general ...
0
votes
1
answer
98
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 ...
0
votes
0
answers
84
views
How to compute an inverse suffix array $ISA$ from a suffix array $SA$ efficiently?
I cannot help but wonder: how to compute an inverse of a suffix array, preferably in linear time?
For $ISA,ドル it holds that $ISA[SA[i]] = i$.
1
vote
0
answers
126
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
vote
0
answers
95
views
DC3/Skew Suffix Array Algorithm doesn't work for specific cases
When applying the DC3/Skew algorithm to the string yabadabado, I can't quite get it to sort correctly. This issue happens in other cases, but this is a short example to show it.
This first table is ...
0
votes
0
answers
120
views
Finding the longest repeating substring with suffix arrays
I found an implementation of suffix arrays here (not sure if it's the most efficient so if there's any better I'd be glad to know).
For a given string:
...
1
vote
0
answers
126
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 ...
0
votes
1
answer
105
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 ...
3
votes
3
answers
699
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
0
answers
294
views
How to find the length of maximum subarray sum in segment tree query?
Problem: Given an array with size$\ n $: for each$\ a[i] ,ドル it denotes the value of the house. You are given the task to build the wall that saves the house that is not exceed$\ w $ length. What is ...
3
votes
1
answer
300
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 ...
0
votes
1
answer
85
views
Suffix array construction algorithm linear complexity constant
A non-recursive linear Suffix Array construction algorithm is presented in this thesis: Linear-time Suffix Sorting. The author claims that, overall, the algorithm runs at $O(n)$. While it is well ...
2
votes
0
answers
384
views
Fast generalised suffix array construction: lower than O(n^2 log n)
There is a lot in the literature about linear time constructions for suffix arrays; DC3, radixSA46, and more...
However, these, I believe, are only for suffix arrays; with a single string input.
Are ...
2
votes
2
answers
281
views
Storage cost of a suffix array
MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size ...
2
votes
0
answers
68
views
What is an easy-to-implement linear or non-quadratic suffix array construction algorithm?
The algorithm described here in "Linear Work Suffix Array Construction" (2006) has compact C++ code that is too abstract for me to follow. Is that still the current easy-to-implement linear algorithm? ...