[Guido]
Maybe someone reading this can finish the Wikipedia page on Two-Way Search? The code example trails off with a function with some incomprehensible remarks and then a TODO..
Yes, the Wikipedia page is worse than useless in its current state, although some of the references it lists are helpful. This is a much better summary: http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 but, I believe, still far too telegraphic. The original paper is by far the best account I've seen so far, with complete code and exhaustive explanations and proofs. Even examples ;-) But here's the thing: I don't believe this algorithm this _can_ be reduced to an elevator pitch. Excruciating details appear to be fundamental at every step, and I've seen nothing yet anywhere approaching an "intuitive explanation" :-( What happens instead is that you run it on the hardest cases you can dream up, and your jaw drops in amazement :-)