Exact string matching algorithms

Monday 22 March 2004

One of the things that fascinates me about computer science is that the seemingly simple can be studied for long enough to find the non-obvious in it. Consider the problem of finding a small string somewhere inside a larger one. It’s easy to do it a simple way: for every character in the larger string, see if it is an exact copy of the smaller string. Turns out, though, that people have been coming up with better and better ways to perform this simple feat, so that now there are dozens of different algorithms.

Christian Charras and Thierry Lecroq have gathered them all together, with explanations, pictures, and even Java animations of the algorithms at work: Exact String Matching Algorithms.

Comments

Add a comment:

Ignore this:
Leave this empty:
Name is required. Either email or web are required. Email won't be displayed and I won't spam you. Your web site won't be indexed by search engines.
Don't put anything here:
Leave this empty:
URLs auto-link and some tags are allowed: <a><b><i><p><br><pre>.