Backtracking example1

Let’s say you want to find the word following “foo” in the string “Food is on the foo table.”:

#!/usr/bin/perl

# Example of backtracking algorithm

use 5.006;

use strict;

use warnings;

$_ = "Food is on the foo table.";

if ( /b(foo)s+(w+)/i ) {

print "$2 follows $1.n";

}

When the match runs, the first part of the regular expression (b(foo) ) finds a possible match right at the beginning of the string, and loads up $1 with “Foo”. However, as soon as the matching engine sees that there’s no whitespace following the  “Foo” that it had saved in $1, it realizes its mistake and starts over again one character after where it had the tentative match. This time it goes all the way until the next occurrence of “foo”. The complete regular expression matches this time and you get the expected output of “table follows foo.”

Still more examples to come …keep watching

Thanks

Author: Pradeep Pant

Software Engineer

Leave a Reply

Your email address will not be published. Required fields are marked *