I need to find the longest non-overlapping repeated substring in a String. I have the suffix tree and suffix array of the string available. When overlapping is allowed, the answer is trivial (deep...

I've recently been updating my knowledge of algorithms and have been reading up on suffix arrays. Every text I've read has defined them as an array of suffixes over a single search string, but some...

I am attempting to complete the Algorithm's on Strings course on Coursera and am stuck on the method to construct an LCP array described in this video: https://www.coursera.org/learn/algorithms-on...

I'm looking for an efficient data structure to do String/Pattern Matching on an really huge set of strings. I've found out about tries, suffix-trees and suffix-arrays. But I couldn't find an ready-...

I'm really trying to understand an example on how to construct a good suffix table for a given pattern. The problem is, I'm unable to wrap my head around it. I've looked at numerous examples, but d...

Foreword: My question is mainly an algorithmic question, so even if you are not familiar with suffix and LCP arrays you can probably help me. In this paper it is described how to efficiently use s...

What would be the best approach (performance-wise) in solving this problem? I was recommended to use suffix trees. Is this the best approach?

I have read that the Longest Common Prefix (LCP) could be used to find the number of occurrences of a pattern in a string. Specifically, you just need to create the suffix array of the text, sort ...

How to find the sum of length of Longest Common Prefixes of all pairs of substrings of a given string. For eg answer for string "aba" is 8. |s|<=1e5.

Can we use a factor-oracle with suffix link (paper here) to compute the longest common substring of multiple strings? Here, substring means any part of the original string. For example "abc" is the...

I have been learning suffix arrays creation, & i understand that We first sort all suffixes according to first character, then according to first 2 characters, then first 4 characters and so on...

I've sucessfully implemented a BWT stage (using regular string sorting) for a compression testbed I'm writing. I can apply the BWT and then inverse BWT transform and the output matches the input. N...

Today I am trying to create suffix arrays using scala. I was able to do it with massive lines of code but then I heard that it can be created by using only few lines by using zipping and sorting. ...

Can someone explain how this code for constructing the LCP from a suffix array works? suffixArr[] is an array such that suffixArr[i] holds the value of the index in the string for the suffix with r...

I'm looking at the pseudo-code given in figure 3 of the original paper introducing suffix arrays "SUFFIX ARRAYS: A NEW METHOD FOR ON-LINE STRING SEARCHES". I can't figure out the logic for lines ...

After quite a bit of reading, I have figured out what a suffix array and LCP array represents. Suffix array: Represents the _lexicographic rank of each suffix of an array. LCP array : Contains th...

From Section 15.2 of Programming Pearls The C codes can be viewed here: http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c When I implement it in Python using suffix-array: example = open("iliad...

I'm looking for a fast suffix-array construction algorithm. I'm more interested in ease of implementation and raw speed than asymptotic complexity (I know that a suffix array can be constructed by ...

We need to find shortest uncommon substring between two strings i.e. if we have two strings a and b so we need to find the length of shortest substring of a that is not a substring of b. How to so...

I just wanna know, when a suffix tree is superior to an enhanced suffix array. After reading Replacing suffix trees with enhanced suffix arrays i don't see a reason to use suffix trees anymore. Some...

I'm reading the block sort algorithm from the Burrows and Wheeler paper. This a step of the algorithm: Suppose S= abracadabra Initialize an array W of N words W[0, ... , N - 1], such that W[i] co...

A suffix array will index all the suffixes for a given list of strings, but what if you're trying to index all the possible unique substrings? I'm a bit new at this, so here's an example of what I ...

Here's a very simple way to build an suffix array from a string in python: def sort_offsets(a, b): return cmp(content[a:], content[b:]) content = "foobar baz foo" suffix_array.sort(cmp=sort_offs...