What about this? I keep a list of possible positions, I delete non-matching positions recursively character by character. If I make the string much longer (
x 100_000), it still runs only for 8 seconds on my box.
#!/usr/bin/perl
use warnings;
use strict;
use feature qw(say);
# 1 2 3 4
# 0123456789012345678901234567890123456789012345
# | | | | | |
our $string = '1234561234123x561234123x61234x3456123412345x1';
our $pattern = '123456';
our $pattern_length = length $pattern;
our %results;
search(0, 0, [0 .. length($string) - 1]);
say for sort { $a <=> $b } keys %results;
sub search {
my ($p_pos, $s_pos, $positions) = @_;
return if $p_pos > $pattern_length;
return unless @$positions;
if ($p_pos == $pattern_length) {
undef @results{@$positions};
return;
}
my $char = substr $pattern, $p_pos, 1;
search($p_pos + 1, $s_pos + 1,
[ grep {
my $ch = substr($string, $s_pos + $_, 1);
$char eq $ch or 'x' eq $ch;
} @$positions ]);
search($p_pos + 2, $s_pos + 1,
[ grep substr($string, $s_pos + $_, 1) eq 'x',
@$positions ]);
}
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.