Skip to main content
7 votes

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 ...
Yuval Filmus's user avatar
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 ...
Pratik Deoghare's user avatar
2 votes

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 ...
aaaaajack's user avatar
  • 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 ...
pcpthm's user avatar
  • 2,792
1 vote

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 ...
D.W.'s user avatar
  • 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. ...
gnasher729's user avatar
  • 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 ...
Dmitri Urbanowicz's user avatar
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 ...
orlp's user avatar
  • 13.6k

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