1. Find Pattern in Text
2. Brute-force
	1. Check for pattern starting at each text position
	2. Worst case ~MN
	3. Need backup of the text to go backwards
3. Knuth-Morris-Pratt
	1. Don’t need to back up text pointer
	2. DFA
		1. Deterministic Finite State Automaton
		2. Exactly one transition for each possibility
		3. Accept if sequence of transitions leads to halt state
		4. State: number of characters in pattern that have been matched
		5. Need to precompute dfa[][], text pointer i never decrements, could use input stream
	3. Build DFA table
		1. if mismatch, the last j-1 characters of input are pat[1…j-1] followed by mismatch c
		2. Simulate pat[1…j-1] on DFA and take transition c
		3. require j steps
		4. Take only constant time if we maintain state X
		5. For each state j if mismatch, set dfa[c][j] = dfa[c][X], then update X = dfa[pat.charAt(j)][X]
		6. Time space (RM), M+N chacter search accesses
4. Boyer-Moore
	1. Scan character in pattern from right to left
	2. Can skip as many as M text chars when finding one not in the pattern
	3. How much to skip
		1. Precompute index of rightmost occurence of character c in pattern (-1 if character not in pattern)
		2. skip the length of the pattern - (the above)
	4. N/M character compares
	5. Worst case ~MN
5. Rabin-Karp
	1. Modular hashing
	2. Computer a hash of pattern characters (take a big prime and compute reminder)
	3. for each i computer a hash of text character i to M+i-1
	4. If pattern hash = text substring hash, check for a match
	5. Honer’s method: linear time method to evaluate degree M polynomial
		1. (ti*10^(M-1) + t(i+m-1))%Q
		2. Reuse the previous hashed result, subtract the unused trailing character, to compute the next character
	6. Monte-carlo version:no check
	7. Las-vegas version:check even hash matches
	8. Linear time
	9. Easy to extended to complex situations (2d)
	10. Direct suffix search may be slow (arithmetic ops slower than char compares)