patternMinor
Isn't this Commentz-Walter algorithm buggy?
Viewed 0 times
thisbuggyalgorithmcommentzwalterisn
Problem
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
An example of an input that fails my implementation tests is to find the string
Can anyone put me right?
Pseudocode of search algorithm:
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 failsCan anyone put me right?
Pseudocode of search algorithm:
Solution
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)Context
StackExchange Computer Science Q#128263, answer score: 2
Revisions (0)
No revisions yet.