String data structures

Question 1

Trie (idea)

Answer 1

Store all strings in a tree, each node has k (number of different letters in language) pointers to the next letter in the word, each word ends by pointing to a special node ($ for example).

Question 2

Pattern searching algorithms (name and runtime) T- text, P- patterns

Answer 2

Naive - 𝑂(|𝑇|∙|𝑃|)
KMP - 𝑂(|𝑇|+|𝑃|)
Boyer & Moor - 𝑂(|𝑇|+|𝑃|)
Karp & Rabin - 𝑂(|𝑇|+|𝑃|)

Question 3

Suffix tree (idea, time, space)

Answer 3

A Trie tree that includes all of the suffixes of the inserted words, each suffix pointing to the index. Enables Searching for patterns in O(P) time. O(T^2) space.

Question 4

Suffix tree space complexity improvement (how)

Answer 4

Combine all nodes that don’t lead to an index together, leading to O(T) space complexity.