I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible position.

The paper is available here, though it is a scanned printout from 40 years ago. I have also found a better quality pseudocode for the core search loop (image below). But it seems that neither description of the algorithm provides a way to 'back out' of a dead end: The current trie node v is only ever assigned to its own child. It seems that there is a missing step: once the inner loop has exhausted the possibility of a match, the current node should be changed.

An example of an input that fails my implementation tests is to find the string bb in abb: The search begins on the first b, finds that ab is invalid, and fails

Can anyone put me right?

Pseudocode of search algorithm:

Commentz-Walter pseudocode


I figured it out, you have to reset v to root at the same time as you reset j to 0 (in fact if you just add depth to your node, you can skip j and just use v.depth)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.