Skip to main content

# Tag Info

## Hot answers tagged suffix-trees

7 votes
Accepted

### Where did Don Knuth say that suffix trees were the "Algorithm of the Year 1973?"

The source of the quote seems to be From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction by Giegerich and Kurtz. On page 347, at the start of Section 6 (An ...
• 278k
2 votes

### Understanding Martin Farach's suffix tree algorithm

Not a complete answer but I hope this helps. re : Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list ...
• 1,741
2 votes
Accepted

### find if a string is periodic using a suffix tree, and prove it

It's wrong. Consider $aaaabb$, so you'll find that $aaa$ repeat twice and consider it as an answer, while it is obviously not. Check each suffix with length $n>l\ge\frac{n}{2}$. If it's also a ...
• 515
2 votes

### What is the time complexity of determining maximal overlaps between bitmap images?

For a pair of matrices $A, B$, $B$ maximally overlaps $A$ at a position if and only if certain two rectangular sub-matrices of $A$ and $B$ match. It is not clear how to use the two-dimensional suffix ...
• 2,792
1 vote
Accepted

### Find repeated patterns in a string via lossy compression

You can solve this using dynamic programming. I will describe it in terms of constructing a graph and finding shortest paths in the graph, which is roughly equivalent. Let $A[1..n]$ be the input ...
• 162k
1 vote

### 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]

Find the last occurence of any h, i, j, k, l, n. If none is found, there is no solution. If the last one is found at position r, then the string we are looking for must start at position before r. ...
• 30.7k
1 vote

### Longest common substring many strings to one

Let's assume you have already built suffix tree for string $S$. Then for any string $T$ you can find $\mathtt{LCS}(S, T)$ in $\mathcal{O}(|T|)$ time, $\mathcal{O}(1)$ space, and read-only access to ...
• 1,073
1 vote

### Find shortest prefix to generate original string by overlapping

What you are looking for is called the quasiperiod of a string. If such a string has a quasiperiod of $|S|$ it is called superprimitive, and can not be covered by a substring. A method for computing ...
• 13.6k

Only top scored, non community-wiki answers of a minimum length are eligible