Longest common suffix
- Task
Write a function to find the longest common suffix string amongst an array of strings.
- Metrics
- Counting
- Word frequency
- Letter frequency
- Jewels and stones
- I before E except after C
- Bioinformatics/base count
- Count occurrences of a substring
- Count how many vowels and consonants occur in a string
- Remove/replace
- XXXX redacted
- Conjugate a Latin verb
- Remove vowels from a string
- String interpolation (included)
- Strip block comments
- Strip comments from a string
- Strip a set of characters from a string
- Strip whitespace from a string -- top and tail
- Strip control codes and extended characters from a string
- Anagrams/Derangements/shuffling
- Word wheel
- ABC problem
- Sattolo cycle
- Knuth shuffle
- Ordered words
- Superpermutation minimisation
- Textonyms (using a phone text pad)
- Anagrams
- Anagrams/Deranged anagrams
- Permutations/Derangements
- Find/Search/Determine
- ABC words
- Odd words
- Word ladder
- Semordnilap
- Word search
- Wordiff (game)
- String matching
- Tea cup rim text
- Alternade words
- Changeable words
- State name puzzle
- String comparison
- Unique characters
- Unique characters in each string
- Extract file extension
- Levenshtein distance
- Palindrome detection
- Common list elements
- Longest common suffix
- Longest common prefix
- Compare a list of strings
- Longest common substring
- Find common directory path
- Words from neighbour ones
- Change e letters to i in words
- Non-continuous subsequences
- Longest common subsequence
- Longest palindromic substrings
- Longest increasing subsequence
- Words containing "the" substring
- Sum of the digits of n is substring of n
- Determine if a string is numeric
- Determine if a string is collapsible
- Determine if a string is squeezable
- Determine if a string has all unique characters
- Determine if a string has all the same characters
- Longest substrings without repeating characters
- Find words which contains all the vowels
- Find words which contain the most consonants
- Find words which contains more than 3 vowels
- Find words whose first and last three letters are equal
- Find words with alternating vowels and consonants
- Formatting
- Substring
- Rep-string
- Word wrap
- String case
- Align columns
- Literals/String
- Repeat a string
- Brace expansion
- Brace expansion using ranges
- Reverse a string
- Phrase reversals
- Comma quibbling
- Special characters
- String concatenation
- Substring/Top and tail
- Commatizing numbers
- Reverse words in a string
- Suffixation of decimal numbers
- Long literals, with continuations
- Numerical and alphabetical suffixes
- Abbreviations, easy
- Abbreviations, simple
- Abbreviations, automatic
- Song lyrics/poems/Mad Libs/phrases
- Mad Libs
- Magic 8-ball
- 99 bottles of beer
- The Name Game (a song)
- The Old lady swallowed a fly
- The Twelve Days of Christmas
- Tokenize
- Text between
- Tokenize a string
- Word break problem
- Tokenize a string with escaping
- Split a character string based on change of character
- Sequences
11l
F lcs(sa)
I sa.empty
R ‘’
I sa.len == 1
R sa[0]
V min_len = min(sa.map(s -> s.len))
L(i) 1 .. min_len
V p = sa[0][(len)-i]
L(j) 1 .< sa.len
I sa[j][(len)-i] != p
R sa[0][(len)-i+1..]
R sa[0][(len)-min_len..]
print(lcs([‘11Sunday’, ‘2Sunday’]))
print(lcs([‘Sunday’, ‘Monday’, ‘Tuesday’]))
print(lcs([‘Sunday’, ‘Monday’, ‘Tuesday’, ‘day’]))
print(lcs([‘Sondag’, ‘Maandag’, ‘Dinsdag’, ‘Woensdag’]))
- Output:
Sunday day day dag
Action!
DEFINE PTR="CARD"
BYTE Func Equals(CHAR ARRAY a,b)
BYTE i
IF a(0)#b(0) THEN
RETURN (0)
FI
FOR i=1 TO a(0)
DO
IF a(i)#b(i) THEN
RETURN (0)
FI
OD
RETURN (1)
BYTE FUNC CommonLength(PTR ARRAY texts BYTE count)
CHAR ARRAY t
BYTE i,len
IF count=0 THEN
RETURN (0)
FI
len=255
FOR i=0 TO count-1
DO
t=texts(i)
IF t(0)<len THEN
len=t(0)
FI
OD
RETURN (len)
PROC Suffix(PTR ARRAY texts BYTE count CHAR ARRAY res)
CHAR ARRAY t(100)
CHAR ARRAY tmp
BYTE i,len,found
IF count=1 THEN
SCopy(res,texts(0))
RETURN
FI
len=CommonLength(texts,count)
WHILE len>0
DO
tmp=texts(0)
SCopyS(res,tmp,tmp(0)-len+1,tmp(0))
found=1
FOR i=1 TO count-1
DO
tmp=texts(i)
SCopyS(t,texts(i),tmp(0)-len+1,tmp(0))
IF Equals(res,t)#1 THEN
found=0 EXIT
FI
OD
IF found THEN
RETURN
FI
len==-1
OD
res(0)=0
RETURN
PROC Test(PTR ARRAY texts BYTE count)
BYTE i
CHAR ARRAY res(100)
Suffix(texts,count,res)
Print("lcs(")
IF count>0 THEN
FOR i=0 TO count-1
DO
PrintF("""%S""",texts(i))
IF i<count-1 THEN
Print(",")
FI
OD
FI
PrintF(")=""%S""%E",res)
RETURN
PROC Main()
CHAR ARRAY
t1="Sunday", t2="Monday", t3="Tuesday", t4="Wednesday",
t5="Thursday", t6="Friday", t7="Saturday",
t8="throne", t9="throne", t10="dungeon", t11="",
t12="prefix", t13="suffix"
PTR ARRAY texts(20)
texts(0)=t1 texts(1)=t2 texts(2)=t3
texts(3)=t4 texts(4)=t5 texts(5)=t6
texts(6)=t7
Test(texts,7)
texts(0)=t8 texts(1)=t9
Test(texts,2)
texts(0)=t8 texts(1)=t10
Test(texts,2)
texts(0)=t8 texts(1)=t11 texts(2)=t9
Test(texts,3)
texts(0)=t10
Test(texts,1)
texts(0)=t11
Test(texts,1)
Test(texts,0)
texts(0)=t12 texts(1)=t13
Test(texts,2)
RETURN
- Output:
Screenshot from Atari 8-bit computer
lcs("Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday")="day" lcs("throne","throne")="throne" lcs("throne","dungeon")="" lcs("throne","","throne")="" lcs("dungeon")="dungeon" lcs("")="" lcs()="" lcs("prefix","suffix")="fix"
Ada
with Ada.Strings.Unbounded;
with Ada.Text_Io.Unbounded_IO;
procedure Longest_Common_Suffix is
use Ada.Text_Io;
use Ada.Text_Io.Unbounded_Io;
use Ada.Strings.Unbounded;
subtype Ustring is Unbounded_String;
function "+"(S : String) return Ustring
renames To_Unbounded_String;
type String_List is array (Positive range <>) of Ustring;
function Longest_Suffix (List : String_List) return Ustring is
Suffix : Ustring := List (List'First);
begin
for A in List'First + 1 .. List'Last loop
declare
Word : Ustring renames List (A);
Found : Boolean := False;
Len : constant Natural :=
Natural'Min (Length (Suffix), Length (Word));
begin
for P in reverse 1 .. Len loop
if Tail (Suffix, P) = Tail (Word, P) then
Suffix := Tail (Word, P);
Found := True;
exit;
end if;
end loop;
if not Found then
Suffix := +"";
end if;
end;
end loop;
return Suffix;
end Longest_Suffix;
procedure Put (List : String_List) is
begin
Put ("[");
for S of List loop
Put ("'"); Put (S); Put ("' ");
end loop;
Put ("]");
end Put;
procedure Test (List : String_List) is
begin
Put (List); Put (" -> '");
Put (Longest_Suffix (List));
Put ("'");
New_Line;
end Test;
Case_1 : constant String_List := (+"baabababc", +"baabc", +"bbbabc");
Case_2 : constant String_List := (+"baabababc", +"baabc", +"bbbazc");
Case_3 : Constant String_List := (+"Sunday", +"Monday", +"Tuesday",
+"Wednesday", +"Thursday", +"Friday",
+"Saturday");
Case_4 : constant String_List := (+"longest", +"common", +"suffix");
Case_5 : constant String_List := (1 => +"suffix");
Case_6 : Constant String_List := (1 => +"");
begin
Test (Case_1);
Test (Case_2);
Test (Case_3);
Test (Case_4);
Test (Case_5);
Test (Case_6);
end Longest_Common_Suffix;
- Output:
['baabababc' 'baabc' 'bbbabc' ] -> 'abc' ['baabababc' 'baabc' 'bbbazc' ] -> 'c' ['Sunday' 'Monday' 'Tuesday' 'Wednesday' 'Thursday' 'Friday' 'Saturday' ] -> 'day' ['longest' 'common' 'suffix' ] -> '' ['suffix' ] -> 'suffix' ['' ] -> ''
ALGOL 68
Based on the Algol 68 sample for the Longest Common Prefix task.
# find the longest common suffix of two strings #
PRIO COMMONSUFFIX = 1;
OP COMMONSUFFIX = ( STRING a, b )STRING:
BEGIN
INT a pos := UPB a; INT a min = LWB a;
INT b pos := UPB b; INT b min = LWB b;
WHILE
IF a pos < a min OR b pos < b min THEN FALSE
ELSE a[ a pos ] = b[ b pos ]
FI
DO
a pos -:= 1; b pos -:= 1
OD;
a[ a pos + 1 : UPB a ]
END # COMMONSUFFIX # ;
# get the length of a string #
OP LEN = ( STRING a )INT: ( UPB a + 1 ) - LWB a;
# find the longest common suffix of an array of STRINGs #
OP LONGESTSUFFIX = ( []STRING list )STRING:
IF UPB list < LWB list
THEN
# no elements #
""
ELIF UPB list = LWB list
THEN
# only one element #
list[ LWB list ]
ELSE
# more than one element #
STRING suffix := list[ LWB list ] COMMONSUFFIX list[ 1 + LWB list ];
FOR pos FROM 2 + LWB list TO UPB list WHILE suffix /= "" DO
STRING next suffix := list[ pos ] COMMONSUFFIX suffix;
IF LEN next suffix < LEN suffix
THEN
# this element has a smaller common suffix #
suffix := next suffix
FI
OD;
suffix
FI ;
# test the LONGESTSUFFIX operator #
PROC test suffix = ( []STRING list, STRING expected result )VOID:
BEGIN
STRING suffix = LONGESTSUFFIX list;
print( ( "longest common suffix of (" ) );
FOR pos FROM LWB list TO UPB list DO print( ( " """, list[ pos ], """" ) ) OD;
print( ( " ) is: """, suffix, """ "
, IF suffix = expected result THEN "as expected" ELSE "NOT AS EXPECTED" FI
, newline
)
)
END # test suffix # ;
[ 1 : 0 ]STRING empty list; # for recent versions of Algol 68G, can't just put "()" for an empty list #
BEGIN
test suffix( ( "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" ), "day" );
test suffix( ( "throne", "throne" ), "throne" );
test suffix( ( "throne", "dungeon" ), "" );
test suffix( ( "throne", "", "throne" ), "" );
test suffix( ( "cheese" ), "cheese" );
test suffix( ( "" ), "" );
test suffix( empty list, "" );
test suffix( ( "prefix", "suffix" ), "fix" );
test suffix( ( "send", "lend" ), "end" )
END
- Output:
longest common suffix of ( "Sunday" "Monday" "Tuesday" "Wednesday" "Thursday" "Friday" "Saturday" ) is: "day" as expected longest common suffix of ( "throne" "throne" ) is: "throne" as expected longest common suffix of ( "throne" "dungeon" ) is: "" as expected longest common suffix of ( "throne" "" "throne" ) is: "" as expected longest common suffix of ( "cheese" ) is: "cheese" as expected longest common suffix of ( "" ) is: "" as expected longest common suffix of ( ) is: "" as expected longest common suffix of ( "prefix" "suffix" ) is: "fix" as expected longest common suffix of ( "send" "lend" ) is: "end" as expected
APL
lcs ← ⌽+/∘(∧\)∘⊃∘(∧/2=/(⌊/≢¨)↑¨⌽¨)↑⌽∘⊃
- Output:
lcs 'baabababc' 'baabc' 'bbbabc' abc lcs 'baabababc' 'baabc' 'bbbazc' c lcs 'Sunday' 'Monday' 'Tuesday' 'Wednesday' 'Thursday' 'Friday' 'Saturday' day lcs 'longest' 'common' 'suffix' lcs ,⊂''
AppleScript
Procedural
The simplest solution in AppleScript seems to be to reverse the strings, apply the AppleScriptObjC solution for the Longest common prefix task, and reverse the result.
use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later
use framework "Foundation"
on longestCommonSuffix(textList)
-- Eliminate any non-texts from the input.
if (textList's class is record) then return ""
set textList to (textList as list)'s text
if (textList is {}) then return ""
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ""
repeat with i from 1 to (count textList)
set item i of textList to (reverse of characters of item i of textList) as text
end repeat
set lcs to (reverse of characters of longestCommonPrefix(textList)) as text
set AppleScript's text item delimiters to astid
return lcs
end longestCommonSuffix
on longestCommonPrefix(textList)
-- Eliminate any non-texts from the input.
if (textList's class is record) then return ""
set textList to (textList as list)'s text
if (textList is {}) then return ""
-- Convert the AppleScript list to an NSArray of NSStrings.
set stringArray to current application's class "NSArray"'s arrayWithArray:(textList)
-- Compare the strings case-insensitively using a built-in NSString method.
set lcp to stringArray's firstObject()
repeat with i from 2 to (count stringArray)
set lcp to (lcp's commonPrefixWithString:(item i of stringArray) options:(current application's NSCaseInsensitiveSearch))
if (lcp's |length|() is 0) then exit repeat
end repeat
-- Return the NSString result as AppleScript text.
return lcp as text
end longestCommonPrefix
-- Tests and results:
longestCommonSuffix({"throne", "sousaphone"}) --> "one"
longestCommonSuffix({"prefix", "suffix"}) --> "fix"
longestCommonSuffix({"remark", "spark", "aardvark"}) --> "ark"
longestCommonSuffix({"ectoplasm", "banana"}) --> ""
Functional
and for more productivity, and higher re-use of library functions, we can write a functional definition (rather than a procedure):
------------------- LONGEST COMMON SUFFIX ------------------
-- longestCommonSuffix :: [String] -> String
on longestCommonSuffix(xs)
if 1 < length of xs then
reverse of map(my fst, ¬
takeWhile(my allSame, ¬
transpose(map(my |reverse|, xs)))) as text
else
xs as text
end if
end longestCommonSuffix
---------------------------- TESTS --------------------------
on run
script test
on |λ|(s)
set xs to words of s
showList(xs) & " -> '" & longestCommonSuffix(xs) & "'"
end |λ|
end script
unlines(map(test, {¬
"throne sousaphone tone", ¬
"prefix suffix infix", ¬
"remark spark aardvark lark", ¬
"ectoplasm banana brick"}))
end run
--------------------- GENERIC FUNCTIONS --------------------
-- all :: (a -> Bool) -> [a] -> Bool
on all(p, xs)
-- True if p holds for every value in xs
tell mReturn(p)
set lng to length of xs
repeat with i from 1 to lng
if not |λ|(item i of xs, i, xs) then return false
end repeat
true
end tell
end all
-- allSame :: [a] -> Bool
on allSame(xs)
if 2 > length of xs then
true
else
script p
property h : item 1 of xs
on |λ|(x)
h = x
end |λ|
end script
all(p, rest of xs)
end if
end allSame
-- comparing :: (a -> b) -> (a -> a -> Ordering)
on comparing(f)
script
on |λ|(a, b)
tell mReturn(f)
set fa to |λ|(a)
set fb to |λ|(b)
if fa < fb then
-1
else if fa > fb then
1
else
0
end if
end tell
end |λ|
end script
end comparing
-- concatMap :: (a -> [b]) -> [a] -> [b]
on concatMap(f, xs)
set lng to length of xs
set acc to {}
tell mReturn(f)
repeat with i from 1 to lng
set acc to acc & (|λ|(item i of xs, i, xs))
end repeat
end tell
return acc
end concatMap
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- fst :: (a, b) -> a
on fst(tpl)
if class of tpl is record then
|1| of tpl
else
item 1 of tpl
end if
end fst
-- intercalate :: String -> [String] -> String
on intercalate(delim, xs)
set {dlm, my text item delimiters} to ¬
{my text item delimiters, delim}
set str to xs as text
set my text item delimiters to dlm
str
end intercalate
-- justifyLeft :: Int -> Char -> String -> String
on justifyLeft(n, cFiller)
script
on |λ|(strText)
if n > length of strText then
text 1 thru n of (strText & replicate(n, cFiller))
else
strText
end if
end |λ|
end script
end justifyLeft
-- length :: [a] -> Int
on |length|(xs)
set c to class of xs
if list is c or string is c then
length of xs
else
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
end if
end |length|
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- maximumBy :: (a -> a -> Ordering) -> [a] -> a
on maximumBy(f, xs)
set cmp to mReturn(f)
script max
on |λ|(a, b)
if a is missing value or cmp's |λ|(a, b) < 0 then
b
else
a
end if
end |λ|
end script
foldl(max, missing value, xs)
end maximumBy
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- Egyptian multiplication - progressively doubling a list, appending
-- stages of doubling to an accumulator where needed for binary
-- assembly of a target length
-- replicate :: Int -> a -> [a]
on replicate(n, a)
set out to {}
if 1 > n then return out
set dbl to {a}
repeat while (1 < n)
if 0 < (n mod 2) then set out to out & dbl
set n to (n div 2)
set dbl to (dbl & dbl)
end repeat
return out & dbl
end replicate
-- reverse :: [a] -> [a]
on |reverse|(xs)
if class of xs is text then
(reverse of characters of xs) as text
else
reverse of xs
end if
end |reverse|
-- showList :: [a] -> String
on showList(xs)
script show
on |λ|(x)
if text is class of x then
"'" & x & "'"
else
x as text
end if
end |λ|
end script
if {} ≠ xs then
"[" & intercalate(", ", map(show, xs)) & "]"
else
"[]"
end if
end showList
-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on take(n, xs)
set c to class of xs
if list is c then
if 0 < n then
items 1 thru min(n, length of xs) of xs
else
{}
end if
else if string is c then
if 0 < n then
text 1 thru min(n, length of xs) of xs
else
""
end if
else if script is c then
set ys to {}
repeat with i from 1 to n
set v to |λ|() of xs
if missing value is v then
return ys
else
set end of ys to v
end if
end repeat
return ys
else
missing value
end if
end take
-- takeWhile :: (a -> Bool) -> [a] -> [a]
-- takeWhile :: (Char -> Bool) -> String -> String
on takeWhile(p, xs)
if script is class of xs then
takeWhileGen(p, xs)
else
tell mReturn(p)
repeat with i from 1 to length of xs
if not |λ|(item i of xs) then ¬
return take(i - 1, xs)
end repeat
end tell
return xs
end if
end takeWhile
-- transpose :: [[a]] -> [[a]]
on transpose(rows)
set w to length of maximumBy(comparing(|length|), rows)
set paddedRows to map(justifyLeft(w, "x"), rows)
script cols
on |λ|(_, iCol)
script cell
on |λ|(row)
item iCol of row
end |λ|
end script
concatMap(cell, paddedRows)
end |λ|
end script
map(cols, item 1 of rows)
end transpose
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set str to xs as text
set my text item delimiters to dlm
str
end unlines
- Output:
['throne', 'sousaphone', 'tone'] -> 'one' ['prefix', 'suffix', 'infix'] -> 'fix' ['remark', 'spark', 'aardvark', 'lark'] -> 'ark' ['ectoplasm', 'banana', 'brick'] -> ''
Arturo
lcs: function [l][
ret: ""
idx: 0
lst: map l => reverse
while [true] [
thisLetter: ""
loop lst 'word [
if idx=size word -> return reverse ret
if thisLetter="" -> thisLetter: get split word idx
if thisLetter<>get split word idx -> return reverse ret
]
ret: ret ++ thisLetter
idx: idx + 1
]
]
print lcs ["Sunday" "Monday" "Tuesday" "Wednesday" "Thursday" "Friday" "Saturday"]
print lcs ["throne" "throne"]
print lcs ["throne" "dungeon"]
print lcs ["cheese"]
print lcs ["prefix" "suffix"]
- Output:
day throne cheese fix
AutoHotkey
Longest_common_suffix(data){
for num, v in StrSplit(data.1)
for i, word in data
if (SubStr(word, 1-num) <> SubStr(data.1, 1-num))
return num=1 ? "" : SubStr(word, 2-num)
return SubStr(word, 1-num)
}
Examples:
MsgBox % ""
. "`n" Longest_common_suffix(["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"])
. "`n" Longest_common_suffix(["throne", "throne"])
. "`n" Longest_common_suffix(["throne", "dungeon"])
. "`n" Longest_common_suffix(["throne", "", "throne"])
. "`n" Longest_common_suffix(["cheese"])
. "`n" Longest_common_suffix([""])
. "`n" Longest_common_suffix(["prefix", "suffix"])
. "`n" Longest_common_suffix(["bar", "foobar"])
return
- Output:
day throne cheese fix bar
AWK
# syntax: GAWK -f LONGEST_COMMON_SUFFIX.AWK
BEGIN {
arr1[++n1] = "AAbcd,Abcd,abcd,bcd"
arr1[++n1] = "11Sunday,2Sunday"
arr1[++n1] = "Sunday,Monday"
arr1[++n1] = "Sunday,Monday,day"
arr1[++n1] = "Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday"
arr1[++n1] = "crucifix,infix,prefix,suffix"
arr1[++n1] = "identical,identical"
arr1[++n1] = ","
arr1[++n1] = "this,has,nothing,in,common"
for (i=1; i<=n1; i++) {
n2 = split(arr1[i],arr2,",")
min_wid = 999
for (j=1; j<=n2; j++) {
leng = length(arr2[j])
if (min_wid > leng) {
min_wid = leng
min_col = j
}
}
cols = 0
for (j=1; j<=min_wid; j++) {
delete arr3
for (k=1; k<n2; k++) {
arr3[substr(arr2[k],length(arr2[k])+1-j)] = ""
arr3[substr(arr2[k+1],length(arr2[k+1])+1-j)] = ""
}
if (length(arr3) == 1) {
cols++
}
}
printf("'%s' : '%s'\n",arr1[i],(cols == 0) ? "" : substr(arr2[min_col],length(arr2[min_col])+1-cols))
}
exit(0)
}
- Output:
'AAbcd,Abcd,abcd,bcd' : 'bcd' '11Sunday,2Sunday' : 'Sunday' 'Sunday,Monday' : 'nday' 'Sunday,Monday,day' : 'day' 'Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday' : 'day' 'crucifix,infix,prefix,suffix' : 'fix' 'identical,identical' : 'identical' ',' : '' 'this,has,nothing,in,common' : ''
BaCon
FUNCTION Common_Suffix$(data$)
LOCAL x, size
LOCAL delim$
REPEAT
delim$ = ""
INCR size
FOR x = 1 TO AMOUNT(data$)
delim$ = APPEND$(delim$, 0, RIGHT$(TOKEN$(data$, x), size))
NEXT
UNTIL AMOUNT(UNIQ$(delim$)) <> 1
RETURN RIGHT$(TOKEN$(data$, 1), size-1)
ENDFUNCTION
PRINT "The common suffix is: '", Common_Suffix$("baabababc baabc bbbabc"), "'"
PRINT "The common suffix is: '", Common_Suffix$("Monday Tuesday Wednesday Thursday Friday Saturday Sunday"), "'"
PRINT "The common suffix is: '", Common_Suffix$("longest common suffix"), "'"
PRINT "The common suffix is: '", Common_Suffix$("prefix suffix"), "'"
PRINT "The common suffix is: '", Common_Suffix$(""), "'"
- Output:
The common suffix is: 'abc' The common suffix is: 'day' The common suffix is: '' The common suffix is: 'fix' The common suffix is: ''
BASIC
BASIC256
dim pre$ = {"baabababc","baabc","bbbabc"}
longitud = pre$[?]
print "There are "; longitud; " words in the list: ";
for n = 0 to longitud -1
print pre$[n]; " ";
next n
print chr(10); "The longest common suffix is: "; lcs$(pre$)
end
function lcs$ (list$)
if list$[?] = -1 then
lcs$ = ""
return
end if
refe$ = list$[0]
for i = 0 to list$[?] -1
if length(list$[i]) < length(refe$) then refe$ = list$[i]
next
for i = 1 to length(refe$)
sub$ = right(refe$, i)
for j = 0 to list$[?] -1
if right(list$[j], i) <> sub$ then
lcs$ = right(refe$, i - 1)
return
end if
next
next
return refe$
end function
- Output:
There are 3 words in the list: baabababc baabc bbbabc The longest common suffix is: abc
QBasic
DECLARE FUNCTION lcs$ (list$())
DIM pre$(2) '= {"baabababc","baabc","bbbabc"} 'abc
pre$(0) = "baabababc"
pre$(1) = "baabc"
pre$(2) = "bbbabc"
longitud = UBOUND(pre$)
PRINT "There are"; longitud; "words in the list: ";
FOR n = 1 TO longitud
PRINT pre$(n); " ";
NEXT n
PRINT
PRINT "The longest common suffix is: "; lcs$(pre$())
FUNCTION lcs$ (list$())
IF UBOUND(list$) = -1 THEN lcs$ = "": EXIT FUNCTION
ref$ = list$(0)
FOR i = 1 TO UBOUND(list$)
IF LEN(list$(i)) < LEN(ref$) THEN ref$ = list$(i)
NEXT
FOR i = 1 TO LEN(ref$)
sub$ = RIGHT$(ref$, i)
FOR j = 0 TO UBOUND(list$)
IF RIGHT$(list$(j), i) <> sub$ THEN lcs$ = RIGHT$(ref$, i - 1): EXIT FUNCTION
NEXT
NEXT
lcs$ = ref$
END FUNCTION
- Output:
There are 3 words in the list: baabababc baabc bbbabc The longest common suffix is: abc
QB64
The QBasic solution works without any changes.
BQN
LCS ← ∧`⌾⌽∘(∧˝·=˝˘2⊸↕)⊸/⟜⊏0‿0↓(>(⌊´≠¨)-⊸↑¨⊢)
LCS¨ ⟨
⟨"Friday", "Saturday", "Sunday"⟩
⟨"throne", "throne"⟩
⟨"throne", "dungeon"⟩
⟨"throne", "", "throne"⟩
⟨"cheese"⟩
⟨""⟩
⟨⟩
⟨"prefix", "suffix"⟩
⟨"foo", "foobar"⟩
⟩
- Output:
⟨ "day" "throne" ⟨⟩ ⟨⟩ "cheese" ⟨⟩ ⟨⟩ "fix" ⟨⟩ ⟩
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node_t {
char *elem;
int length;
struct node_t *next;
} node;
node *make_node(char *s) {
node *t = malloc(sizeof(node));
t->elem = s;
t->length = strlen(s);
t->next = NULL;
return t;
}
void append_node(node *head, node *elem) {
while (head->next != NULL) {
head = head->next;
}
head->next = elem;
}
void print_node(node *n) {
putc('[', stdout);
while (n != NULL) {
printf("`%s` ", n->elem);
n = n->next;
}
putc(']', stdout);
}
char *lcs(node *list) {
int minLen = INT_MAX;
int i;
char *res;
node *ptr;
if (list == NULL) {
return "";
}
if (list->next == NULL) {
return list->elem;
}
for (ptr = list; ptr != NULL; ptr = ptr->next) {
minLen = min(minLen, ptr->length);
}
if (minLen == 0) {
return "";
}
res = "";
for (i = 1; i < minLen; i++) {
char *suffix = &list->elem[list->length - i];
for (ptr = list->next; ptr != NULL; ptr = ptr->next) {
char *e = &ptr->elem[ptr->length - i];
if (strcmp(suffix, e) != 0) {
return res;
}
}
res = suffix;
}
return res;
}
void test(node *n) {
print_node(n);
printf(" -> `%s`\n", lcs(n));
}
void case1() {
node *n = make_node("baabababc");
append_node(n, make_node("baabc"));
append_node(n, make_node("bbbabc"));
test(n);
}
void case2() {
node *n = make_node("baabababc");
append_node(n, make_node("baabc"));
append_node(n, make_node("bbbazc"));
test(n);
}
void case3() {
node *n = make_node("Sunday");
append_node(n, make_node("Monday"));
append_node(n, make_node("Tuesday"));
append_node(n, make_node("Wednesday"));
append_node(n, make_node("Thursday"));
append_node(n, make_node("Friday"));
append_node(n, make_node("Saturday"));
test(n);
}
void case4() {
node *n = make_node("longest");
append_node(n, make_node("common"));
append_node(n, make_node("suffix"));
test(n);
}
void case5() {
node *n = make_node("suffix");
test(n);
}
void case6() {
node *n = make_node("");
test(n);
}
int main() {
case1();
case2();
case3();
case4();
case5();
case6();
return 0;
}
- Output:
[`baabababc` `baabc` `bbbabc` ] -> `abc` [`baabababc` `baabc` `bbbazc` ] -> `c` [`Sunday` `Monday` `Tuesday` `Wednesday` `Thursday` `Friday` `Saturday` ] -> `day` [`longest` `common` `suffix` ] -> `` [`suffix` ] -> `suffix` [`` ] -> ``
C++
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
std::string lcs(const std::vector<std::string>& strs) {
std::vector<std::string::const_reverse_iterator> backs;
std::string s;
if (strs.size() == 0) return "";
if (strs.size() == 1) return strs[0];
for (auto& str : strs) backs.push_back(str.crbegin());
while (backs[0] != strs[0].crend()) {
char ch = *backs[0]++;
for (std::size_t i = 1; i<strs.size(); i++) {
if (backs[i] == strs[i].crend()) goto done;
if (*backs[i] != ch) goto done;
backs[i]++;
}
s.push_back(ch);
}
done:
reverse(s.begin(), s.end());
return s;
}
void test(const std::vector<std::string>& strs) {
std::cout << "[";
for (std::size_t i = 0; i<strs.size(); i++) {
std::cout << '"' << strs[i] << '"';
if (i != strs.size()-1) std::cout << ", ";
}
std::cout << "] -> `" << lcs(strs) << "`\n";
}
int main() {
std::vector<std::string> t1 = {"baabababc", "baabc", "bbabc"};
std::vector<std::string> t2 = {"baabababc", "baabc", "bbazc"};
std::vector<std::string> t3 =
{"Sunday", "Monday", "Tuesday", "Wednesday", "Friday", "Saturday"};
std::vector<std::string> t4 = {"longest", "common", "suffix"};
std::vector<std::string> t5 = {""};
std::vector<std::string> t6 = {};
std::vector<std::string> t7 = {"foo", "foo", "foo", "foo"};
std::vector<std::vector<std::string>> tests = {t1,t2,t3,t4,t5,t6,t7};
for (auto t : tests) test(t);
return 0;
}
- Output:
["baabababc", "baabc", "bbabc"] -> `abc` ["baabababc", "baabc", "bbazc"] -> `c` ["Sunday", "Monday", "Tuesday", "Wednesday", "Friday", "Saturday"] -> `day` ["longest", "common", "suffix"] -> `` [""] -> `` [] -> `` ["foo", "foo", "foo", "foo"] -> `foo`
Cowgol
include "cowgol.coh";
include "strings.coh";
sub lcs(arr: [[uint8]], len: intptr): (s: [uint8]) is
if len == 0 then
s := "";
return;
elseif len == 1 then
s := [arr];
return;
end if;
s := [arr];
var slen := StrLen(s);
s := s + slen;
arr := @next arr;
len := len - 1;
while len > 0 and slen > 0 loop
var c := [arr];
var clen := StrLen(c);
c := c + clen;
if clen > slen then
clen := slen;
end if;
while clen > 0 and [c] == [s] loop
c := @prev c;
s := @prev s;
clen := clen - 1;
end loop;
slen := StrLen(s);
s := s + slen;
arr := @next arr;
len := len - 1;
end loop;
s := s - slen + 1;
end sub;
sub test(arr: [[uint8]], len: intptr) is
var s := arr;
var l := len;
print_char('[');
while l > 0 loop
print_char('"');
print([s]);
print_char('"');
s := @next s;
l := l - 1;
if l > 0 then
print(", ");
end if;
end loop;
print("] -> `");
print(lcs(arr, len));
print("`\n");
end sub;
var test1: [uint8][] := {"baabababc", "baabc", "bbbabc"};
var test2: [uint8][] := {"baabababc", "baabc", "bbbazc"};
var test3: [uint8][] :=
{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday",
"Friday", "Saturday"};
var test4: [uint8][] := {"longest", "common", "suffix"};
var test5: [uint8][] := {""};
var test6: [uint8][] := {};
test(&test1[0], @sizeof test1);
test(&test2[0], @sizeof test2);
test(&test3[0], @sizeof test3);
test(&test4[0], @sizeof test4);
test(&test5[0], @sizeof test5);
test(&test6[0], @sizeof test6);
- Output:
["baabababc", "baabc", "bbbabc"] -> `abc` ["baabababc", "baabc", "bbbazc"] -> `c` ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"] -> `day` ["longest", "common", "suffix"] -> `` [""] -> `` [] -> ``
D
import std.algorithm;
import std.stdio;
string lcs(string[] a) {
auto le = a.length;
if (le == 0) {
return "";
}
if (le == 1) {
return a[0];
}
auto le0 = a[0].length;
auto minLen = a.map!"a.length".reduce!"min(a,b)";
if (minLen == 0) {
return "";
}
auto res = "";
foreach (i; 1..minLen) {
auto suffix = a[0][le0 - i .. $];
foreach (e; a[1..$]) {
if (!e.endsWith(suffix)) {
return res;
}
}
res = suffix;
}
return "";
}
void main() {
auto tests = [
["baabababc", "baabc", "bbbabc"],
["baabababc", "baabc", "bbbazc"],
["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"],
["longest", "common", "suffix"],
["suffix"],
[""]
];
foreach (test; tests) {
writeln(test, " -> `", lcs(test), '`');
}
}
- Output:
["baabababc", "baabc", "bbbabc"] -> `abc` ["baabababc", "baabc", "bbbazc"] -> `c` ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"] -> `day` ["longest", "common", "suffix"] -> `` ["suffix"] -> `suffix` [""] -> ``
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.
- Output:
Input: baabababc baabc bbbabc Longest common suffix = abc
EasyLang
func$ right s$ i .
return substr s$ (len s$ - i + 1) i
.
func$ lcs list$[] .
if len list$[] = 0
return ""
.
ref$ = list$[1]
for s$ in list$[]
if len s$ < len ref$
ref$ = s$
.
.
for i = 1 to len ref$
sub$ = right ref$ i
for s$ in list$[]
if right s$ i <> sub$
return right ref$ (i - 1)
.
.
.
return ref$
.
print lcs [ "Sunday" "Monday" "Tuesday" "Wednesday" "Thursday" "Friday" "Saturday" ]
print lcs [ "throne" "throne" ]
print lcs [ "throne" "dungeon" ]
print lcs [ "cheese" ]
print lcs [ "prefix" "suffix" ]
- Output:
day throne cheese fix
ed
Partially inspired by #sed solution.
H
g/.*/s//&|/
,j
g/\([^|]*\)|\([^|]*\1|\)*$/s//&: \1/
,p
Q
- Output:
$ ed -s longest-suffix.input < longest-suffix.ed Newline appended Sunday|Monday|Tuesday|: day
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 .
- Output:
"abc" "c" ""
FreeBASIC
Dim As String pre(1 To ...) = {"baabababc","baabc","bbbabc"}
Dim As Integer longitud = Ubound(pre)
Dim As Integer lenList(longitud)
Dim As Integer n, m, longest
Dim As String temp
Function rever(Byval text As String) As String
Dim As String text2 = text
Dim As Integer x, lt = Len(text)
For x = 0 To lt Shr 1 - 1
Swap text2[x], text2[lt - x - 1]
Next x
Return text2
End Function
Print "There are"; longitud; " words in the list: ";
For n = 1 To longitud
Print pre(n); " ";
temp = pre(n)
pre(n) = rever(temp)
lenList(n) = Len(pre(n))
Next n
For m = 1 To lenList(1)
Dim As String sub1 = Mid(pre(1),1,m)
Dim As String sub2 = Mid(pre(2),1,m)
Dim As String sub3 = Mid(pre(3),1,m)
If sub1 = sub2 And sub2 = sub3 Then longest = m
Next m
Dim As String longPrefix = Mid(pre(1),1,longest)
longPrefix = rever(longPrefix)
Print !"\n\nThe longest common suffix is: "; longPrefix
Sleep
- Output:
There are 3 words in the list: baabababc baabc bbbabc The longest common suffix is: abc
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))
}
}
- 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:
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"
]
]
- Output:
day dag
J
lcs =: [: |. [: ({. #~ [: *./\ [: *./ 2 =/\ ]) >@(|. each)
test1 =: 'baabababc';'baabc';'bbabc'
test2 =: 'baabababc';'baabc';'bbazc'
test3 =: 'Sunday';'Monday';'Tuesday';'Wednesday';'Friday';'Saturday'
test4 =: 'longest';'common';'suffix'
tests =: test1;test2;test3;<test4
echo@((1{":),' -> ', 1{":@<@lcs) each tests
exit''
- Output:
│baabababc│baabc│bbabc│ -> │abc│ │baabababc│baabc│bbazc│ -> │c│ │Sunday│Monday│Tuesday│Wednesday│Friday│Saturday│ -> │day│ │longest│common│suffix│ -> ││
Java
import java.util.List;
public class App {
private static String lcs(List<String> a) {
var le = a.size();
if (le == 0) {
return "";
}
if (le == 1) {
return a.get(0);
}
var le0 = a.get(0).length();
var minLen = le0;
for (int i = 1; i < le; i++) {
if (a.get(i).length() < minLen) {
minLen = a.get(i).length();
}
}
if (minLen == 0) {
return "";
}
var res = "";
var a1 = a.subList(1, a.size());
for (int i = 1; i < minLen; i++) {
var suffix = a.get(0).substring(le0 - i);
for (String e : a1) {
if (!e.endsWith(suffix)) {
return res;
}
}
res = suffix;
}
return "";
}
public static void main(String[] args) {
var tests = List.of(
List.of("baabababc", "baabc", "bbbabc"),
List.of("baabababc", "baabc", "bbbazc"),
List.of("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"),
List.of("longest", "common", "suffix"),
List.of("suffix"),
List.of("")
);
for (List<String> test : tests) {
System.out.printf("%s -> `%s`\n", test, lcs(test));
}
}
}
- Output:
[baabababc, baabc, bbbabc] -> `abc` [baabababc, baabc, bbbazc] -> `c` [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday] -> `day` [longest, common, suffix] -> `` [suffix] -> `suffix` [] -> ``
JavaScript
(() => {
'use strict';
// --------------- LONGEST COMMON SUFFIX ---------------
// longestCommonSuffix :: [String] -> String
const longestCommonSuffix = xs => (
1 < xs.length ? (
takeWhile(allSame)(
transpose(xs.map(reverse))
).map(fst).reverse()
) : xs
).join('');
// ----------------------- TEST ------------------------
const main = () =>
fTable('Longest common suffix:\n')(unwords)(
quoted("'")
)(longestCommonSuffix)([
'throne saxophone tone',
'prefix suffix infix',
'remark spark aardvark lark',
'ectoplasm banana brick'
].map(words))
// ----------------- GENERIC FUNCTIONS -----------------
// allSame :: [a] -> Bool
const allSame = xs =>
2 > xs.length || (
h => xs.slice(1).every(x => h === x)
)(xs[0]);
// fst :: (a, b) -> a
const fst = tpl =>
// First member of a pair.
tpl[0];
// fTable :: String -> (a -> String) ->
// (b -> String) -> (a -> b) -> [a] -> String
const fTable = s =>
// Heading -> x display function ->
// fx display function ->
// f -> values -> tabular string
xShow => fxShow => f => xs => {
const
ys = xs.map(xShow),
w = Math.max(...ys.map(length));
return s + '\n' + zipWith(
a => b => a.padStart(w, ' ') + ' -> ' + b
)(ys)(
xs.map(x => fxShow(f(x)))
).join('\n');
};
// length :: [a] -> Int
const length = xs =>
// Returns Infinity over objects without finite
// length. This enables zip and zipWith to choose
// the shorter argument when one is non-finite,
// like cycle, repeat etc
'GeneratorFunction' !== xs.constructor
.constructor.name ? xs.length : Infinity;
// map :: (a -> b) -> [a] -> [b]
const map = f =>
// The list obtained by applying f
// to each element of xs.
// (The image of xs under f).
xs => [...xs].map(f);
// reverse :: [a] -> [a]
const reverse = xs =>
'string' !== typeof xs ? (
xs.slice(0).reverse()
) : xs.split('').reverse().join('');
// str :: a -> String
const str = x =>
Array.isArray(x) && x.every(
v => ('string' === typeof v) && (1 === v.length)
) ? (
x.join('')
) : x.toString();
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => 'GeneratorFunction' !== xs
.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// takeWhile :: (a -> Bool) -> [a] -> [a]
// takeWhile :: (Char -> Bool) -> String -> String
const takeWhile = p =>
xs => (
n => xs.slice(
0, 0 < n ? until(
i => n === i || !p(xs[i])
)(i => 1 + i)(0) : 0
)
)(xs.length);
// transpose :: [[a]] -> [[a]]
const transpose = xss => {
// If some of the rows are shorter than the following rows,
// their elements are skipped:
// > transpose [[10,11],[20],[],[30,31,32]] == [[10,20,30],[11,31],[32]]
const go = xss =>
0 < xss.length ? (() => {
const
h = xss[0],
t = xss.slice(1);
return 0 < h.length ? [
[h[0]].concat(t.reduce(
(a, xs) => a.concat(
0 < xs.length ? (
[xs[0]]
) : []
),
[]
))
].concat(go([h.slice(1)].concat(
t.map(xs => xs.slice(1))
))) : go(t);
})() : [];
return go(xss);
};
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = p => f => x => {
let v = x;
while (!p(v)) v = f(v);
return v;
};
// unwords :: [String] -> String
const unwords = xs =>
// A space-separated string derived
// from a list of words.
xs.join(' ');
// quoted :: Char -> String -> String
const quoted = c =>
// A string flanked on both sides
// by a specified quote character.
s => c + s + c;
// words :: String -> [String]
const words = s =>
// List of space-delimited sub-strings.
s.split(/\s+/);
// zipWithList :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
// A list constructed by zipping with a
// custom function, rather than with the
// default tuple constructor.
xs => ys => ((xs_, ys_) => {
const lng = Math.min(length(xs_), length(ys_));
return take(lng)(xs_).map(
(x, i) => f(x)(ys_[i])
);
})([...xs], [...ys]);
// MAIN ---
return main();
})();
- Output:
Longest common suffix: throne saxophone tone -> 'one' prefix suffix infix -> 'fix' remark spark aardvark lark -> 'ark' ectoplasm banana brick -> ''
jq
Works with gojq, the Go implementation of jq
This entry uses `longest_common_prefix` from Longest_common_suffix#jq and so the definition is not repeated here.
# Input: an array of strings
def longest_common_suffix:
def r: explode | reverse | implode;
if length == 0 then "" # by convention
elif length == 1 then .[0] # for speed
else map(r)
| longest_common_prefix
| r
end;
Test Cases
def test:
["baabababc","baabc","bbbabc"],
["baabababc","baabc","bbbazc"],
[""],
[],
["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"],
["throne","cone", "bone"]
| "\(.) => \(longest_common_suffix)";
test
- Output:
["baabababc","baabc","bbbabc"] => abc ["baabababc","baabc","bbbazc"] => c [""] => [] => ["Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"] => day ["throne","cone","bone"] => one
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([""]))
- Output:
abc c
Kotlin
fun lcs(a: List<String>): String {
val le = a.size
if (le == 0) {
return ""
}
if (le == 1) {
return a[0]
}
val le0 = a[0].length
var minLen = le0
for (i in 1 until le) {
if (a[i].length < minLen) {
minLen = a[i].length
}
}
if (minLen == 0) {
return ""
}
var res = ""
val a1 = a.subList(1, a.size)
for (i in 1..minLen) {
val suffix = a[0].substring(le0 - i)
for (e in a1) {
if (!e.endsWith(suffix)) {
return res
}
}
res = suffix
}
return ""
}
fun main() {
val tests = listOf(
listOf("baabababc", "baabc", "bbbabc"),
listOf("baabababc", "baabc", "bbbazc"),
listOf("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"),
listOf("longest", "common", "suffix"),
listOf("suffix"),
listOf("")
)
for (test in tests) {
println("$test -> `${lcs(test)}`")
}
}
- Output:
[baabababc, baabc, bbbabc] -> `abc` [baabababc, baabc, bbbazc] -> `c` [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday] -> `day` [longest, common, suffix] -> `` [suffix] -> `suffix` [] -> ``
Ksh
#!/bin/ksh
# Longest common suffix
# # Variables:
#
typeset -a arr1=( "Sunday" "Monday" "Tuesday" "Wednesday" "Thursday" "Friday" "Saturday" )
typeset -a arr2=( "baabababc" "baabc" "bbbabc" )
typeset -a arr3=( "baabababc" "babc" "bbbabc" )
typeset -a arr4=( "longest" "common" "suffix" )
typeset -a arr5=( "suffix" )
typeset -a arr6=( "" )
# # Functions:
#
# # Function _minlenele(arr) - return the shortest element in an array
#
function _minlenele {
typeset _arr ; nameref _arr="$1"
typeset _min _i ; integer _i
_min=${_arr[0]}
for ((_i=1; _i<${#_arr[*]}; _i++)); do
(( ${#_arr[_i]} < ${#_min} )) && _min=${_arr[_i]}
done
echo "${_min}"
}
######
# main #
######
for array in arr1 arr2 arr3 arr4 arr5 arr6; do
nameref arr=${array}
printf "\n( %s ) -> " "${arr[*]}"
suffix=$(_minlenele arr)
for ((j=${#suffix}; j>0; j--)); do
for ((i=0; i<${#arr[*]}; i++)); do
[[ ${arr[i]%${suffix: -${j}}} == ${arr[i]} ]] && continue 2
done
printf "'%s'" ${suffix: -${j}}
break
done
typeset +n arr
done
echo
- Output:
( Sunday Monday Tuesday Wednesday Thursday Friday Saturday ) -> 'day' ( baabababc baabc bbbabc ) -> 'abc' ( baabababc babc bbbabc ) -> 'babc' ( longest common suffix ) -> ( suffix ) -> 'suffix' ( ) ->
Mathematica /Wolfram Language
ClearAll[LCS]
LCS[x_List] := Module[{l, s},
If[Length[x] > 0,
l = Min[StringLength /@ x];
s = Characters[StringTake[x, -l]];
s //= Transpose;
l = LengthWhile[Reverse@s, Apply[SameQ]];
StringTake[First[x], -l]
,
""
]
]
LCS[{"throne", "sousaphone"}]
LCS[{"prefix", "suffix"}]
LCS[{"remark", "spark", "aardvark"}]
LCS[{"throne", "", "throne"}]
LCS[{"throne", "throne"}]
LCS[{"cheese"}]
LCS[{""}]
LCS[{}]
LCS[{"ectoplasm", "banana"}]
- Output:
"one" "fix" "ark" "" "throne" "cheese" "" "" ""
Nim
import sequtils, strformat, strutils
func lcs(list: varargs[string]): string =
if list.len == 0: return
result = list[0]
for i in 1..list.high:
var newLength = 0
for j in 1..result.len:
if j > list[i].len or list[i][^j] != result[^j]:
break
inc newLength
result = result[^newLength..^1]
proc test(list: varargs[string]) =
let lst = list.mapIt('"' & it & '"').join(", ")
echo &"lcs({lst}) = \"{lcs(list)}\""
test("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday")
test("throne", "throne")
test("throne", "dungeon")
test("cheese")
test("")
test()
test("prefix", "suffix")
test("send", "lend")
- Output:
lcs("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday") = "day" lcs("throne", "throne") = "throne" lcs("throne", "dungeon") = "" lcs("cheese") = "cheese" lcs("") = "" lcs() = "" lcs("prefix", "suffix") = "fix" lcs("send", "lend") = "end"
Perl
Based on Longest_common_prefix Perl entry.
use strict;
use warnings;
use feature 'say';
sub lcs {
for (0..$#_) { $_[$_] = reverse $_[$_] }
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)]}';
}
- 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:
with javascript_semantics 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
- 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:
'''Longest common suffix'''
from itertools import takewhile
from functools import reduce
# 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 reduce(
firstCharPrepended,
takewhile(
allSame,
zip(*(reversed(x) for x in xs))
),
''
)
# -------------------------- TEST --------------------------
# 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)
)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
day dag
Quackery
commonprefix
is defined at Longest common prefix#Quackery.
[ [] swap
witheach
[ reverse nested join ]
commonprefix
reverse ] is commonsuffix ( [ --> $ )
$ "monday tuesday wednesday thursday friday saturday sunday"
nest$ commonsuffix echo$
- Output:
day
Raku
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',
''
- 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.
/*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)
- output when using the default input:
There are 3 words in the list: baabababc baabc bbbabc The longest common suffix is: abc
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
- Output:
Input: baabababc baabc bbbabc Longest common suffix = abc
Ruby
Testcases taken from Go.
tests = [["baabababc", "baabc", "bbbabc"],
["baabababc", "baabc", "bbbazc"],
["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"],
["longest", "common", "suffix"],
["suffix"],
[""],
]
def lcs(ar)
i = (0..ar.first.size).detect{|s| ar.all?{|word| word.end_with? ar.first[s..-1]} }
ar.first[i..-1]
end
tests.each{|test| p lcs(test) }
- Output:
"abc" "c" "day" "" "suffix" ""
Rust
fn longestcommonsuffix(strings: &[&str]) -> String {
let mut n = 0;
let nmax = strings.iter().map(|x| x.len()).min().unwrap();
if nmax == 0 {
return String::from("");
}
'a: while n <= nmax {
for s in strings {
if s.len() < n + 1 {
break 'a;
}
let ch1 = &s[s.len() - 1 - n..=s.len() - 1 - n];
let s2 = strings[strings.len() - 1];
if ch1 != &s2[s2.len() - 1 - n..=s2.len() - 1 - n] {
break 'a;
}
}
n += 1;
}
return strings[0][strings[0].len() - n..].to_string();
}
fn main() {
let tests = [["baabababc", "baabc", "bbbabc"].to_vec(),
["baabababc", "baabc", "bbbazc"].to_vec(),
["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"].to_vec(),
["longest", "common", "suffix"].to_vec(),
["suffix"].to_vec(),
[""].to_vec()];
for t in tests {
println!("The longest common suffix of {:?} is \"{}\".", t, longestcommonsuffix(&t.to_vec()));
}
}
- Output:
The longest common suffix of ["baabababc", "baabc", "bbbabc"] is "abc". The longest common suffix of ["baabababc", "baabc", "bbbazc"] is "c". The longest common suffix of ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"] is "day". The longest common suffix of ["longest", "common", "suffix"] is "". The longest common suffix of ["suffix"] is "suffix". The longest common suffix of [""] is "".
sed
$q
N
s/\(.*\)\(\n\).*\1$/\2\1/
D
$ printf '%s\n' Sunday '' Monday Tuesday | sed -f suffix.sed $ printf '%s\n' Sunday Monday Tuesday | sed -f suffix.sed day $ printf '%s\n' Sunday Monday | sed -f suffix.sed nday
Standard ML
val lcs =
let
val commonSuffix = fn (s0, s1) =>
let
val rec pairTakeREq = fn (0, _) => s0 | (_, 0) => s1 | (i, j) =>
let
val i' = i - 1 and j' = j - 1
in
if String.sub (s0, i') = String.sub (s1, j')
then pairTakeREq (i', j')
else String.extract (s0, i, NONE)
end
in
pairTakeREq (size s0, size s1)
end
in
fn [] => "" | x :: xs => foldl commonSuffix x xs
end
V (Vlang)
fn lcs(a []string) string {
// Special cases first
match a.len {
0 {
return ""
}
1 {
return a[0]
}
else {}
}
le0 := a[0].len
mut min_len := le0
for i in 1..a.len {
if a[i].len < min_len {
min_len = a[i].len
}
}
if min_len == 0 {
return ""
}
mut res := ""
a1 := a[1..]
for i := 1; i <= min_len; i++ {
suffix := a[0][le0-i..]
for e in a1 {
if e.index(suffix) or {0} + suffix.len != e.len {
return res
}
}
res = suffix
}
return res
}
// Normally something like this would be a Testlcs function in *_test.go
// and use the testing package to report failures.
fn main() {
for l in [
["baabababc", "baabc", "bbbabc"],
["baabababc", "baabc", "bbbazc"],
["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"],
["longest", "common", "suffix"],
["suffix"],
[""],
] {
println("lcs($l) = ${lcs(l)}")
}
}
- Output:
Same as Go entry
Wren
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))\"")
- Output:
[baabababc, baabc, bbbabc] -> "abc" [baabababc, baabc, bbbazc] -> "c" [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday] -> "day" [longest, common, suffix] -> "" [suffix] -> "suffix" [] -> ""
XPL0
include xpllib; \for StrRev
proc LCS(N, Strs); \Show longest common suffix
int N; char Strs;
int I, J, C;
[for I:= 0 to N-1 do \work with reversed strings
StrRev(@Strs(I,0));
J:= 0;
loop [C:= Strs(0,J);
if C = 0 then quit;
for I:= 1 to N-1 do
if Strs(I,J) # C then quit;
J:= J+1;
];
ChOut(0, ^");
for I:= J-1 downto 0 do
ChOut(0, Strs(0,I));
ChOut(0, ^");
CrLf(0);
for I:= 0 to N-1 do \undo reversal (for extra credit?)
StrRev(@Strs(I,0));
];
int Tests, I;
[Tests:= [
[3, "baabababc","baabc","bbbabc"],
[3, "baabababc","baabc","bbbazc"],
[7, "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"],
[3, "longest", "common", "suffix"],
[1, "suffix"],
[1, ""] ];
for I:= 0 to 6-1 do
LCS(Tests(I,0), @Tests(I,1));
]
- Output:
"abc" "c" "day" "" "suffix" ""
- Draft Programming Tasks
- 11l
- Action!
- Ada
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BaCon
- BASIC
- BASIC256
- QBasic
- QB64
- BQN
- C
- C++
- Cowgol
- D
- Delphi
- System.SysUtils
- Types
- EasyLang
- Ed
- Factor
- FreeBASIC
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Ksh
- Mathematica
- Wolfram Language
- Nim
- Perl
- Phix
- Python
- Quackery
- Raku
- REXX
- Ring
- Ruby
- Rust
- Sed
- Standard ML
- V (Vlang)
- Wren
- XPL0