Strings & Automata

• KMP: prefix table to skip work
• Regex: DP, backtracking, and NFA engines
• POSIX: leftmost-longest semantics
• FSM: validate structured input

KMP intuition

• Never backtrack in text
• LPS table encodes pattern self-overlap
• O(n+m) worst-case

Regex DP (lite)

• dp[i][j] = match s[:i] with p[:j]
• Handles '.' and '*'
• Correct and predictable

Backtracking engines

• Depth-first search over regex choices
• Simple but can be exponential
• Catastrophic example: (a+)+b

Thompson NFA

• Compile regex to NFA with epsilon edges
• Track all active states at once
• Avoids exponential blowups

POSIX leftmost-longest

• Earliest start wins
• Among those, longest match wins
• Alternation order does not matter
• Example: "a|aa" on "aa" -> "aa"

Capstone: POSIX regex

• Literals, ., *, +, ?, {m,n}, |, (), []
• Anchors ^ and $
• Return (start, end) of leftmost-longest match

FSM parsing

• States, transitions, accept states
• Ideal for numbers, dates, protocols