Suffix Tree - check!

Which one is the time complexity for the naive algorithm building a suffix tree?

• O(n^2)

• O(n)

• O(n^3)

• O(1)

Which one is the time complexity for the Ukkonen's Algorithm bulding a suffix tree?

• O(n^2)

• O(n)

• O(n^3)

• O(1)

Why do we need a terminator like $, #, *, etc. so that every string could be expressed as a suffix tree?

• When a terminator is added, there's no suffix that is a prefix of another suffix.

• For no reason.

• When a terminator is added, all leaf nodes end with a special character.

• When a terminator is added, it makes a string non-palindrome.

Which statement is not true about the suffix tree?

• This string is abcabc$

• Every internal node has at least 2 children.

• Every edge is labeled by a prefix.

• This string has 6 + 5 + 4 = 15 distinct non-empty substrings.

Suffix tree is prominent in generating substrings since...

• Suffix tree is constructed lexicographically.

• Suffix tree includes the prefixes also.

• A substring is a prefix of a suffix.

• Every edge of suffix tree is labeled by a substring.