15. String matching via careful failure

views comments

Avoiding redundant comparisons
The fail function and finite-state machine
Knuth-Morris-Pratt: O(n) worst-case time
Border of P = any proper prefix of P that is also a suffix of P
fail[j] - 1 is the length of the longest border of P[1..j-1]
Computing fail by searching for P inside itself(!)
Do this with your fingers. Really.
Optimization by pointer-chasing implies O(log m) failures at each text character

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois