Context

”Pattern Matching Problem”

Q: Given input x, p, output ”does p occur in x?”

The most naive way would be

def pattern_match(x,p):
	l = len(p)
	for i in range(len(x)-l):
		if x[i:i+l] == p:
			return 1
	return 0
# or simply "return x in p" lol

And the total operations would be $O(m\cdot n)$

<aside> 💡 Famous Algorithm: Knuth-Morris-Pratt (KMP) algorithm — solves the pattern matching in time $O(m+n)$

</aside>

KMP Algorithm

→ Given P, first find a DFA D on m+1 states

→ For any string x, p occurs in x if and only if D(x) = 1

→ Apply the D on p

Finding the DFA will take O(m) time, and running it on p takes O(n) time

Regular Expressions

Succinct descriptions of large families of patterns

Useful for

→ Programming tool kit

→ Processing text

→ GREP

→ Search + replace in editor

→ …