File Coverage

blib/lib/String/CommonPrefix.pm

Criterion	Covered	Total	%
statement	18	56	32.1
branch	4	26	15.3
condition			n/a
subroutine	5	6	83.3
pod	2	2	100.0
total	29	90	32.2

package String::CommonPrefix;

use 5.010001;
use strict;
use warnings;

use Exporter qw(import);

our $AUTHORITY = 'cpan:PERLANCAR'; # AUTHORITY
our $DATE = '2025-08-02'; # DATE
our $DIST = 'String-CommonPrefix'; # DIST
our $VERSION = '0.021'; # VERSION

our @EXPORT_OK = qw(
                       common_prefix
                       majority_prefix
               );

sub common_prefix {
    return undef unless @_; ## no critic: Subroutines::ProhibitExplicitReturnUndef
    my $i;
  L1:
    for ($i=0; $i < length($_[0]); $i++) {
        for (@_[1..$#_]) {
            if (length($_) < $i) {
                $i--; last L1;
            } else {
                last L1 if substr($_, $i, 1) ne substr($_[0], $i, 1);
            }
        }
    }
    substr($_[0], 0, $i);
}

sub majority_prefix {
    #my $opts = ref($_[0]) eq 'HASH' ? {%{shift}} : {};
    return undef unless @_; ## no critic: Subroutines::ProhibitExplicitReturnUndef

    my @excluded = map {0} @_;
    my $min_items_for_majority = int(@_/2) + 1;
    my $prefix_len = 0;
    while (1) {
        my @items;
        # take the next character from items that are still eligible
        for my $i (0..$#_) {
            my $char;
            if ($excluded[$i]) {
                $char = undef;
            } elsif (length($_[$i]) < $prefix_len) {
                $excluded[$i]++;
                $char = undef;
            } else {
                $char = substr($_[$i], $prefix_len, 1);
            }
            push @items, $char;
        }
        #use DD; dd \@excluded;
        # determine whether there's still a character that belong to the
        # majority
        my %freqs;
        for (@items) { next unless defined; $freqs{$_}++ }
        last unless keys %freqs;
        #use DD; dd \%freqs;
        my @freqs = sort { $freqs{$b} <=> $freqs{$a} } keys %freqs;
        my $majority_char = $freqs[0];
        last if $freqs{$majority_char} < $min_items_for_majority;
        for (0 .. $#items) { next unless defined $items[$_]; unless ($items[$_] eq $majority_char) { $excluded[$_]++ } }
        $prefix_len++;
        #say "D: prefix_len=$prefix_len";
    }

    my $first_included;
    for (0 .. $#_) { unless ($excluded[$_]) { $first_included = $_; last } }
    return undef unless defined $first_included; ## no critic: Subroutines::ProhibitExplicitReturnUndef
    #say "D: first_included=$first_included";
    substr($_[$first_included], 0, $prefix_len);
}

1;
# ABSTRACT: Find prefix common to all strings

__END__