Questions tagged [suffix-array]
The suffix-array tag has no summary.
21 questions
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 ...
- 131
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
86
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$.
- 60
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,187
1
vote
0
answers
96
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 ...
- 111
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
1
vote
0
answers
127
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
0
votes
1
answer
106
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
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", "...
- 31
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 ...
- 1
3
votes
1
answer
301
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
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 ...
- 3
2
votes
0
answers
385
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 ...
- 21
2
votes
2
answers
284
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 ...
- 231
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? ...
- 21
0
votes
2
answers
508
views
Finding A String Using A Suffix Array/Table
Is it possible to find out a string only having its corresponding suffix array/table and knowing that the string contains only, for instance, letters "f", "g", "r"? If so, how is that possible?
- 149
5
votes
0
answers
438
views
Number of distinct substrings
I know how to find the number of distinct substrings for a string (using suffix arrays) and I was wondering if there was a way to find this number for all of its prefixes.
I already have an $O(N^2)$ ...
4
votes
1
answer
896
views
String matching for all suffixes
Given a string $(a_0,a_1,\ldots a_n)$. I want to find the length of the longest common prefix of the substrings $(a_0,a_1,\ldots a_{n-1})$ and $(a_1,a_2,\ldots a_n)$. I know this has atleast $O(n)$ ...
- 141
12
votes
1
answer
3k
views
Counting number of sums from contiguous subarrays of an array
We are given an array $a[1 \ldots n]$ with all $a[i]>0$.
Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a[...
- 253
4
votes
1
answer
8k
views
Number of distinct substrings in a string
From what I have come to understand, the best way to implement it is to use the suffix array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$.
The answer can be obtained by
$$ \...
- 53
18
votes
3
answers
17k
views
Computing the longest common substring of two strings using suffix arrays
After I learned how to build a suffix array in $O(N)$ complexity, I am interested in discovering the applications of the suffix arrays. One of these is finding the longest common substring between two ...
