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 contains most consonants
- Find words which contains more than 3 vowels
- Find words which first and last three letters are equals
- Find words which odd letters are consonants and even letters are vowels or vice_versa
- 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[edit]
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![edit]
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[edit]
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[edit]
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[edit]
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[edit]
Procedural[edit]
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[edit]
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[edit]
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[edit]
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)
}
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[edit]
# 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[edit]
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: ''
C[edit]
#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++[edit]
#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[edit]
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[edit]
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[edit]
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
Factor[edit]
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[edit]
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[edit]
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[edit]
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[edit]
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[edit]
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[edit]
(() => {
'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[edit]
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[edit]
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[edit]
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[edit]
#!/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[edit]
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[edit]
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[edit]
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[edit]
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[edit]
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[edit]
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[edit]
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[edit]
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[edit]
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[edit]
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" ""
sed[edit]
$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[edit]
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)[edit]
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[edit]
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" [] -> ""
- Pages with syntax highlighting errors
- Draft Programming Tasks
- 11l
- Action!
- Ada
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BaCon
- C
- C++
- Cowgol
- D
- Delphi
- System.SysUtils
- Types
- Factor
- FreeBASIC
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Ksh
- Mathematica
- Wolfram Language
- Nim
- Perl
- Phix
- Python
- Quackery
- Raku
- REXX
- Ring
- Ruby
- Sed
- Standard ML
- V (Vlang)
- Wren