Longest common suffix

Longest common suffix is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

The goal is to write a function to find the longest common suffix string amongst an array of strings.

Delphi

Library: System.SysUtils

Library: Types

Translation of: Ring

<lang Delphi> program Longest_common_suffix;

{$APPTYPE CONSOLE}

uses

 System.SysUtils,
 Types;

type

 TStringDynArrayHelper = record helper for TStringDynArray
 private
   class function Compare(const s: string; a: TStringDynArray; subSize: integer):
     Boolean;
 public
   function Reverse(value: string): string;
   function LongestSuffix: string;
   function Join(const sep: char): string;
 end;

{ TStringDynArrayHelper }

class function TStringDynArrayHelper.Compare(const s: string; a: TStringDynArray;

 subSize: integer): Boolean;

var

 i: Integer;

begin

 for i := 0 to High(a) do
   if s <> a[i].Substring(0, subSize) then
     exit(False);
 Result := True;

end;

function TStringDynArrayHelper.Join(const sep: char): string; begin

 Result := string.Join(sep, self);

end;

function TStringDynArrayHelper.LongestSuffix: string; var

 ALength: Integer;
 i, lenMin, longest: Integer;
 ref: string;

begin

 ALength := Length(self);

 // Empty list
 if ALength = 0 then
   exit();

 lenMin := MaxInt;
 for i := 0 to ALength - 1 do
 begin
   // One string is empty
   if self[i].IsEmpty then
     exit();

   self[i] := Reverse(self[i]);

   // Get the minimum length of string
   if lenMin > self[i].Length then
     lenMin := self[i].Length;
 end;

 longest := -1;
 repeat
   inc(longest);
   ref := self[0].Substring(0, longest + 1);
 until not compare(ref, Self, longest + 1) or (longest >= lenMin);

 Result := self[0].Substring(0, longest);
 Result := reverse(Result);

end;

function TStringDynArrayHelper.Reverse(value: string): string; var

 ALength: Integer;
 i: Integer;
 c: Char;

begin

 ALength := value.Length;
 Result := value;

 if ALength < 2 then
   exit;

 for i := 1 to ALength div 2 do
 begin
   c := Result[i];
   Result[i] := Result[ALength - i + 1];
   Result[ALength - i + 1] := c;
 end;

end;

var

 List: TStringDynArray;

begin

 List := ['baabababc', 'baabc', 'bbbabc'];

 Writeln('Input:');
 Writeln(List.Join(#10), #10);
 Writeln('Longest common suffix = ', List.LongestSuffix);

 Readln;

end.

</lang>

Output:

Input:
baabababc
baabc
bbbabc

Longest common suffix = abc

Factor

Works with: Factor version 0.99 2020-07-03

<lang factor>USING: accessors grouping kernel prettyprint sequences sequences.extras ;

! Like take-while, but for matrices and works from the rear.

take-col-while-last ( ... matrix quot: ( ... col -- ... ? ) -- ... new-matrix )

   [ [ <reversed> ] map flip ] dip take-while ; inline

lcs ( seq -- lcs )

   dup first swap [ all-equal? ] take-col-while-last to>> tail* ;

{ "baabababc" "baabc" "bbbabc" } lcs . { "baabababc" "baabc" "bbbazc" } lcs . { "" } lcs .</lang>

Output:

"abc"
"c"
""

Go

Translation of: Wren

<lang go>package main

import (

   "fmt"
   "strings"

)

func lcs(a []string) string {

   le := len(a)
   if le == 0 {
       return ""
   }
   if le == 1 {
       return a[0]
   }
   le0 := len(a[0])
   minLen := le0
   for i := 1; i < le; i++ {
       if len(a[i]) < minLen {
           minLen = len(a[i])
       }
   }
   if minLen == 0 {
       return ""
   }
   res := ""
   a1 := a[1:]
   for i := 1; i <= minLen; i++ {
       suffix := a[0][le0-i:]
       for _, e := range a1 {
           if !strings.HasSuffix(e, suffix) {
               return res
           }
       }
       res = suffix
   }
   return res

}

func main() {

   tests := [][]string{
       {"baabababc", "baabc", "bbbabc"},
       {"baabababc", "baabc", "bbbazc"},
       {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"},
       {"longest", "common", "suffix"},
       {"suffix"},
       {""},
   }
   for _, test := range tests {
       fmt.Printf("%v -> \"%s\"\n", test, lcs(test))
   }

}</lang>

Output:

[baabababc baabc bbbabc] -> "abc"
[baabababc baabc bbbazc] -> "c"
[Sunday Monday Tuesday Wednesday Thursday Friday Saturday] -> "day"
[longest common suffix] -> ""
[suffix] -> "suffix"
[] -> ""

Haskell

This task clearly needs a little more work to bring it up to the usual standard – it's rather underspecified, and bereft of test samples – but one response, for the moment, might be something like: <lang haskell>import Data.List (transpose)

longestCommonSuffix :: [String] -> String longestCommonSuffix =

 foldr (flip (<>) . return . head) [] .
 takeWhile (all =<< (==) . head) . transpose . fmap reverse

main :: IO () main =

 mapM_
   (putStrLn . longestCommonSuffix)
   [ [ "Sunday"
     , "Monday"
     , "Tuesday"
     , "Wednesday"
     , "Thursday"
     , "Friday"
     , "Saturday"
     ]
   , [ "Sondag"
     , "Maandag"
     , "Dinsdag"
     , "Woensdag"
     , "Donderdag"
     , "Vrydag"
     , "Saterdag"
     , "dag"
     ]
   ]</lang>

Output:

day
dag

Julia

<lang julia>function longestcommonsuffix(strings)

   n, nmax = 0, minimum(length, strings)
   nmax == 0 && return ""
   while n <= nmax && all(s -> s[end-n] == strings[end][end-n], strings)
       n += 1
   end
   return strings[1][end-n+1:end]

end

println(longestcommonsuffix(["baabababc","baabc","bbbabc"])) println(longestcommonsuffix(["baabababc","baabc","bbbazc"]))

println(longestcommonsuffix([""]))</lang>

Output:

abc
c

Perl

Based on Longest_common_prefix Perl entry. <lang perl>use strict; use warnings; use feature 'say';

sub lcs {

   for (0..$#_) { $_[$_] = join , reverse split , $_[$_] }
   join , reverse split , (join("\0", @_) =~ /^ ([^\0]*) [^\0]* (?:\0 \1 [^\0]*)* $/sx)[0];

}

for my $words (

 [ <Sunday Monday Tuesday Wednesday Thursday Friday Saturday> ],
 [ <Sondag Maandag Dinsdag Woensdag Donderdag Vrydag Saterdag dag> ],
 [ 2347, 9312347, 'acx5g2347', 12.02347 ],
 [ <longest common suffix> ],
 [ ('one, Hey!', 'three, Hey!', 'ale, Hey!', 'me, Hey!') ],
 [ 'suffix' ],
 [  ]) {
   say qq{'@$words' ==> '@{[lcs(@$words)]}';

}</lang>

Output:

'Sunday Monday Tuesday Wednesday Thursday Friday Saturday' ==> 'day'
'Sondag Maandag Dinsdag Woensdag Donderdag Vrydag Saterdag dag' ==> 'dag'
'2347 9312347 acx5g2347 12.02347' ==> '2347'
'longest common suffix' ==> ''
'one, Hey! three, Hey! ale, Hey! me, Hey!' ==> 'e, Hey!'
'suffix' ==> 'suffix'
'' ==> ''

Phix

Phix allows negative indexes, with -1 as the last element [same as $], and -length(s) the first element of s, so we can just do this: <lang Phix>function longestcommonsuffix(sequence strings)

   string res = ""
   if length(strings) then
       res = strings[1]
       for i=2 to length(strings) do
           string si = strings[i]
           if length(si)<length(res) then
               res = res[-length(si)..$]
           end if
           for j=-1 to -length(res) by -1 do
               if res[j]!=si[j] then
                   res = res[j+1..$]
                   exit
               end if
           end for
           if length(res)=0 then exit end if
       end for
   end if
   return res

end function

sequence tests = {{"baabababc","baabc","bbbabc"},

                 {"baabababc","baabc","bbbazc"},
                 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"},
                 {"longest", "common", "suffix"},
                 {"suffix"},
                 {""}}

for i=1 to length(tests) do

   printf(1,"%v ==> \"%s\"\n",{tests[i],longestcommonsuffix(tests[i])})

end for</lang>

Output:

{"baabababc","baabc","bbbabc"} ==> "abc"
{"baabababc","baabc","bbbazc"} ==> "c"
{"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"} ==> "day"
{"longest","common","suffix"} ==> ""
{"suffix"} ==> "suffix"
{""} ==> ""

Python

Pending a fuller task statement and some test samples:

Works with: Python version 3

<lang python>Longest common suffix

from itertools import takewhile from functools import reduce

1. longestCommonSuffix :: [String] -> String

def longestCommonSuffix(xs):

   Longest suffix shared by all
      strings in xs.
   
   def allSame(cs):
       h = cs[0]
       return all(h == c for c in cs[1:])

   def firstCharPrepended(s, cs):
       return cs[0] + s
   return list(xs) if 2 > len(xs) else reduce(
       firstCharPrepended,
       takewhile(
           allSame,
           zip(*(reversed(x) for x in xs))
       ),
       
   )

1. -------------------------- TEST --------------------------
2. main :: IO ()

def main():

   Test

   samples = [
       [
           "Sunday", "Monday", "Tuesday", "Wednesday",
           "Thursday", "Friday", "Saturday"
       ], [
           "Sondag", "Maandag", "Dinsdag", "Woensdag",
           "Donderdag", "Vrydag", "Saterdag"
       ]
   ]
   for xs in samples:
       print(
           longestCommonSuffix(xs)
       )

1. MAIN ---

if __name__ == '__main__':

   main()</lang>

Output:

day
dag

Raku

Works with: Rakudo version 2020.07

<lang perl6>sub longest-common-suffix ( *@words ) {

   return  unless +@words;
   my $min = @words».chars.min;
   for 1 .. * {
       return @words[0].substr(* - $min) if $_ > $min;
       next if @words».substr(* - $_).Set == 1;
       return @words[0].substr(* - $_ + 1);
   }

}

say "{$_.raku} - LCS: >{longest-common-suffix $_}<" for

 <Sunday Monday Tuesday Wednesday Thursday Friday Saturday>,
 <Sondag Maandag Dinsdag Woensdag Donderdag Vrydag Saterdag dag>,
 ( 2347, 9312347, 'acx5g2347', 12.02347 ),
 <longest common suffix>,
 ('one, Hey!', 'three, Hey!', 'ale, Hey!', 'me, Hey!'),
 'suffix',
 </lang>

Output:

("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday") - LCS: >day<
("Sondag", "Maandag", "Dinsdag", "Woensdag", "Donderdag", "Vrydag", "Saterdag", "dag") - LCS: >dag<
(2347, 9312347, "acx5g2347", 12.02347) - LCS: >2347<
("longest", "common", "suffix") - LCS: ><
("one, Hey!", "three, Hey!", "ale, Hey!", "me, Hey!") - LCS: >e, Hey!<
"suffix" - LCS: >suffix<
"" - LCS: ><

REXX

Essentially,   this REXX version simply reversed the strings,   and then finds the longest common  prefix. <lang rexx>/*REXX program finds the longest common suffix contained in an array of strings. */ parse arg z; z= space(z) /*obtain optional arguments from the CL*/ if z==|z=="," then z='baabababc baabc bbbabc' /*Not specified? Then use the default.*/ z= space(z); #= words(z) /*#: the number of words in the list. */ say 'There are ' # " words in the list: " z zr= reverse(z) /*reverse Z, find longest common prefix*/ @= word(zr, 1); m= length(@) /*get 1st word in reversed string; len.*/

    do j=2  to #;    x= word(zr, j)             /*obtain a word (string) from the list.*/
    t= compare(@, x)                            /*compare to the "base" word/string.   */
    if t==1          then do;  @=;  leave       /*A mismatch of strings?   Then leave, */
                          end                   /*no sense in comparing anymore strings*/
    if t==0 & @==x   then t= length(@) + 1      /*Both strings equal?  Compute length. */
    if t>=m  then iterate                       /*T ≥ M?  Then it's not longest string.*/
    m= t - 1;        @= left(@, max(0, m) )     /*redefine max length & the base string*/
    end   /*j*/

say /*stick a fork in it, we're all done. */ if m==0 then say 'There is no common suffix.'

        else say 'The longest common suffix is: '   right( word(z, 1), m)</lang>

output   when using the default input:

There are  3  words in the list:  baabababc baabc bbbabc

The longest common suffix is:  abc

Ring

<lang ring> load "stdlib.ring"

pre = ["baabababc","baabc","bbbabc"] len = len(pre) lenList = list(len) sub = list(len)

see "Input:" + nl see pre

for n = 1 to len

   temp = pre[n]
   pre[n] = rever(temp)

next

for n = 1 to len

   lenList[n] = len(pre[n])

next

lenList = sort(lenList) lenMax = lenList[1]

for m = 1 to lenMax

   check = 0 
   sub1 = substr(pre[1],1,m)
   sub2 = substr(pre[2],1,m) 
   sub3 = substr(pre[3],1,m)
   if sub1 = sub2 and sub2 = sub3
      check = 1
   ok
   if check = 1
      longest = m
   ok

next

longPrefix = substr(pre[1],1,longest) longPrefix = rever(longPrefix)

see "Longest common suffix = " + longPrefix + nl

func rever(cstr)

    cStr2 = ""
    for x = len(cStr) to 1 step -1 
        cStr2 = cStr2 + cStr[x]
    next
    return cStr2

</lang>

Output:

Input:
baabababc
baabc
bbbabc
Longest common suffix = abc

Wren

<lang ecmascript>var lcs = Fn.new { |a|

   if (a.count == 0) return ""
   if (a.count == 1) return a[0]
   var minLen = a.reduce(a[0].count) { |min, s| (s.count < min) ? s.count : min }
   if (minLen == 0) return ""
   var res = ""
   for (i in 1..minLen) {
       var suffix = a[0][-i..-1]
       for (e in a.skip(1)) {
           if (!e.endsWith(suffix)) return res
       }
       res = suffix
   }
   return res

}

var tests = [

   ["baabababc","baabc","bbbabc"],
   ["baabababc","baabc","bbbazc"],
   ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"],
   ["longest", "common", "suffix"],
   ["suffix"],
   [""]

] for (test in tests) System.print("%(test) -> \"%(lcs.call(test))\"")</lang>

Output:

[baabababc, baabc, bbbabc] -> "abc"
[baabababc, baabc, bbbazc] -> "c"
[Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday] -> "day"
[longest, common, suffix] -> ""
[suffix] -> "suffix"
[] -> ""