String Matching with Finite Automata

https://www.youtube.com/watch?v=M_XpGQyyqIQ

Notes:

1. Finite automata is a state machine. It has start and end state(s). A three letter pattern has four states (s0 to s3). Matched one more letter means state changes. If not match, it will go back to one of the appropriate state. ( Instead, in naive matching, if one letter does not match, it will go back to s0).

2. Finite automata is used to parse in compiler and implement regular expression.

3. State transition table. ( column is alphabet, row is states).

4. Matching time is O(N), preprocessing time depends on implementation.