Prefix suffix

You are given an array of strings. Write a script to find if the two strings ($str1, $str2) in the given array such that $str1 is a prefix and suffix of $str2. Return the total count of such pairs.

Examples

Example 1
Input: @array = ('a', 'aba', 'ababa', 'aa')
Output: 4
$array[0], $array[1]: 'a' is a prefix and suffix of 'aba'
$array[0], $array[2]: 'a' is a prefix and suffix of
   'ababa'
$array[0], $array[3]: 'a' is a prefix and suffix of 'aa'
$array[1], $array[2]: 'aba' is a prefix and suffix of
   'ababa'

Example 2
Input: @array = ('pa', 'papa', 'ma', 'mama')
Output: 2
$array[0], $array[1]: 'pa' is a prefix and suffix of
   'papa'
$array[2], $array[3]: 'ma' is a prefix and suffix of
   'mama'

Example 3
Input: @array = ('abao', 'ab')
Output: 0

Example 4
Input: @array = ('abab', 'abab')
Output: 1
$array[0], $array[1]: 'abab' is a prefix and suffix of
   'abab'

Example 5
Input: @array = ('ab', 'abab', 'ababab')
Output: 3
$array[0], $array[1]: 'ab' is a prefix and suffix of
   'abab'
$array[0], $array[2]: 'ab' is a prefix and suffix of
   'ababab'
$array[1], $array[2]: 'abab' is a prefix and suffix of
   'ababab'

Example 6
Input: @array = ('abc', 'def', 'ghij')
Output: 0

Analysis

This is another challenge in the category of 'why would you ever need to do that?', but let's have a go.

The immediately obvious way is simply to test every pair of strings for this peculiar property. Even with 1000 strings that's only a million tests, and it won't take more than a second or so.

But there are some possible optimisations. Firstly, string A can only be a prefix or suffix of string B if it is no longer than string B. That cuts the number of tests by 2, and since length() is a cheap test I imagine it will cut the runtime by about the same.

And we can (probably) do better still by sorting the strings into length order, so that any any string can only posssibly be a prefix or suffix of itself or a subsequent string.

Another dilemma concerns the check that string A is or isn't a prefix or suffix of string B. The obvious way is:

$string[$b] =~ m|^$string[$a]| and $string[$b] =~ m|$string[$a]$

But you could do:

($string[$b] . $string[$b]) =~ m|^$string[$a].*$string[$a]$| !

which allows for the fact that the prefix and suffix may overlap, for example 'aba', 'ababa'!!, and halves the number of regex matches. That again halves the number of regex matches, and that's what I've submitted.

Try it 

Your input:

@strings =

eg: a banana ba abba nabban bannab

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-06-08
use utf8;     # Week 377 - task 2 - Prefix suffix
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

prefix_suffix('a', 'aba', 'ababa', 'aa');
prefix_suffix('pa', 'papa', 'ma', 'mama');
prefix_suffix('abao', 'ab');
prefix_suffix('abab', 'abab');
prefix_suffix(qw[a aa aaa aaaa aaaaa aaaaaa]);
prefix_suffix(qw[aba ababa]);

sub prefix_suffix {
    
    my (@strings, $count, $i, $j, $explain);
    
    # initialise
    @strings = @_;
    say qq[\nInput:  ('] . join(q[', '], @strings) . q[')];
    
    # sort by length
    @strings = sort {length($a) <=> length($b)} @strings;
    
    # loop over potential pairs
    $count = 0;
    for $i (0 .. $#strings) {
        for $j ($i + 1 .. $#strings) {
            
            # test for prefix and suffix match
            if (($strings[$j] . $strings[$j]) =~ m|^$strings[$i].*$strings[$i]$|) {
                $count ++;
                $explain .= qq[$strings[$i] of $strings[$j], ];
            }
        }
    }       
        
    say qq[Output: $count] . ($count ? qq[ - ] . substr($explain, 0, -2) : '');
}

12 lines of code

Output from script

Input:  ('a', 'aba', 'ababa', 'aa')
Output: 4 - a of aa, a of aba, a of ababa, aba of ababa

Input:  ('pa', 'papa', 'ma', 'mama')
Output: 2 - pa of papa, ma of mama

Input:  ('abao', 'ab')
Output: 0

Input:  ('abab', 'abab')
Output: 1 - abab of abab

Input:  ('a', 'aa', 'aaa', 'aaaa', 'aaaaa', 'aaaaaa')
Output: 15 - a of aa, a of aaa, a of aaaa, a of aaaaa, a of aaaaaa, aa
   of aaa, aa of aaaa, aa of aaaaa, aa of aaaaaa, aaa of aaaa, aaa of
   aaaaa, aaa of aaaaaa, aaaa of aaaaa, aaaa of aaaaaa, aaaaa of
   aaaaaa