Strings & Automata

1. KMP precomputes which array?

LPS (longest prefix-suffix) suffix array Z-order BFS tree

2. Time complexity of KMP for text length n and pattern length m:

O(n+m) O(nm) O(n log m) O(m^2)

3. In regex-lite, '*' means:

4. Why can backtracking regex engines be slow on some patterns?

They can explore exponentially many paths They always build a DFA first They require hashing the input They are limited to fixed-length patterns

5. POSIX regex matching chooses which result when multiple matches exist?

Leftmost-longest Leftmost-first Rightmost-longest Shortest overall

6. In a numeric FSM, which token can appear at most once?

decimal point and exponent digit sign at start whitespace

7. Naive substring search worst-case complexity?