8

For a text of length $n$ we have up to $1+{ n+1 \choose 2}$ different substrings, however there are only $n+1$ suffixes (for every suffix you can pick the position where it starts). I assume you consider the compressed suffix tree (edge labels are words). This is a tree with $n+1$ leaves and every internal node has at least two children. Thus we have less ...


7

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 Explanation of Weiner's Algorithm), they write In this section we go back to the roots and take a look at the “Algorithm of the Year 1973” (D. E. Knuth ...


6

A larger alphabet is usually a drawback. However there are algorithms that can deal with this as long as the alphabet size is $n^{O(1)}$. Ukkonen's algorithm runs only in $O(n)$ if the alphabet size is a constant but it is $O(n \log n)$ without this assumption. However, there are alternatives. You can compute the suffix-array of a text in linear time with ...


4

There is no one complexity for all suffix tree algorithms. There are multiple algorithms, with different running times. It is not helpful to talk about this as though there was only one complexity that applies to all algorithms for computing a suffix tree. If you want to ask what is the running time of an algorithm for this task, you need to specify which ...


4

Here is how to draw the suffix tree for the example $abaab\$$ mentioned in the lecture notes appearing in greybeard's comment. Root. There are two characters appearing in the word, $a,b$, so the root has two outgoing edges, labeled $a$ and $b$. Root->a. Following $a$, we have both characters $a,b$ appearing in the word. So this note has two outgoing edges, ...


2

We prove by induction on $n$ that your sum (with $O(n_1)$ replaced with $n_1$, only taken over non-leaves) is at most $n\log_2 n$. We use the convention $0\log_2 0 = 0$. The base case $n$ = 0 trivially holds, since the sum is empty. Now suppose we have a node with subtrees of sizes $n_1 \leq n_2$; this implies that $n = n_1 + n_2 + 1$. The sum is at most $$ ...


2

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 prefix of $s$, $s$ is periodic and $u$ is the prefix with length $n-l$. If you can't find such suffix $s$ is not periodic. The proof is straight forward: $s[i]=s[i+...


1

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 the suffix tree. Here's pseudocode that finds $M$ - location in the suffix tree (edge plus position on that edge) that corresponds to $\mathtt{LCS}(S, T)$: M := ...


1

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 it in $O(n)$ time is given in "An On-Line String Superprimitivity Test" by Dany Breslauer. You might also be interested in "Of Periods, Quasiperiods, ...


1

Repetitions and periods in strings constitute one of the most fundamental areas of string combinatorics.1 The shortest prefix T of S where, $S = T^k.Q , s.t: k>= 1, Q =$ some prefix of T, then |T| is called the period of string. We say that string w has period p if w[i] = w[i + p] 1 Conventionally, finding T can be done by the Knuth–Morris–Pratt ...


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