#!/usr/bin/env perl
use warnings;
use strict;
use feature qw/say/;
# Takes two arrayrefs of numbers.
#
# Returns the first index in the first one where the second list appears, or
# -1 if not found.
sub find_sublist(++) {
my ($haystack, $needle) = @_;
my $nlen = @$needle;
my $hlen = @$haystack;
return -1 if $hlen == 0 || $nlen == 0;
HAYSTACK_POS:
for (my $n = 0; $n <= $hlen - $nlen; $n++) {
for (my $m = 0; $m < $nlen; $m++) {
if ($haystack->[$n + $m] != $needle->[$m]) {
next HAYSTACK_POS;
}
}
return $n;
}
return -1;
}
# Takes two arrayrefs of numbers.
#
# Returns a list of the starting indexes of the first list
# of every run of the second list. Returns an empty list if
# there are no matches.
sub find_sublists(++) {
my ($haystack, $needle) = @_;
my $nlen = @$needle;
my $hlen = @$haystack;
my @positions;
return @positions if $hlen == 0 || $nlen == 0;
HAYSTACK_POS:
for (my $n = 0; $n <= $hlen - $nlen; $n++) {
for (my $m = 0; $m < $nlen; $m++) {
if ($haystack->[$n + $m] != $needle->[$m]) {
next HAYSTACK_POS;
}
}
push @positions, $n;
}
return @positions;
}
# Takes two arrayrefs of numbers.
#
# Returns a new list that is the first one with every non-overlapping run of
# the second second list removed.
sub remove_sublists(++) {
my @haystack = @{$_[0]};
my $needle = $_[1];
while ((my $pos = find_sublist @haystack, $needle) != -1) {
splice @haystack, $pos, @$needle;
}
return @haystack;
}
my @list1 = (1,2,3,4,5,6,7,8,9);
my @list2 = (4,2,3,4,2,3,4);
my @list3 = (2,3,2,3,2,2,3,2);
say find_sublist(@list1, [2, 3, 4]); # Returns 1
say find_sublist([2,9,3,4], [2,3,4]); # Returns -1
my @positions = find_sublists(@list2, [2,3,4]); # 1,4
say join(",", @positions);
@positions = find_sublists(@list3, [2,3,2]); # 0,2,5
say join(",", @positions);
say join(",", remove_sublists(@list1, [2,3,4])); # 1,5,6,7,8,9
say join(",", remove_sublists(@list3, [2,3,2])); # 3,2
2条答案
按热度按时间q8l4jmvw1#
没有内置的方法,但是很容易编写:
xxslljrj2#
如果输入是可由
perl
的整数表示的数字(如图所示),则可以使用第一个
如何处理重叠:
请注意,如果您可以将输入Map到数字,这也是可行的。
这不是最好的算法,但通过将工作从Perl转移到regex引擎,它应该会非常快。