Backtracking example1
Let’s say you want to find the word following “foo” in the string “Food is on the foo table.”:
</p>
<p style="padding-left:60px;"><span style="color:#008000;">#!/usr/bin/perl</span></p>
<p style="padding-left:60px;"><span style="color:#008000;"> </span></p>
<p style="padding-left:60px;"><span style="color:#008000;"># Example of backtracking algorithm</span></p>
<p style="padding-left:60px;"><span style="color:#993300;"> </span></p>
<p style="padding-left:60px;"><span style="color:#993300;">use 5.006;</span></p>
<p style="padding-left:60px;"><span style="color:#993300;"> </span></p>
<p style="padding-left:60px;"><span style="color:#993300;">use strict;</span></p>
<p style="padding-left:60px;"><span style="color:#993300;"> </span></p>
<p style="padding-left:60px;"><span style="color:#993300;">use warnings;</span></p>
<p style="padding-left:60px;"><span style="color:#993300;"> </span></p>
<p style="padding-left:60px;"><span style="color:#993300;">$_ = "Food is on the foo table.";</span></p>
<p style="padding-left:60px;"><span style="color:#993300;"> </span></p>
<p style="padding-left:60px;"><span style="color:#993300;">if ( /b(foo)s+(w+)/i ) {</span></p>
<p style="padding-left:60px;"><span style="color:#993300;"> </span></p>
<p style="padding-left:60px;"><span style="color:#993300;">print "$2 follows $1.n";</span></p>
<p style="padding-left:30px;"><span style="color:#993300;"> </span></p>
<p style="padding-left:30px;"><span style="color:#993300;"> }</span></p>
<p>
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