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
<lang 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’]))</lang>
- Output:
Sunday day day dag
Action!
<lang 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</lang>
- 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
<lang 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;</lang>
- 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. <lang algol68># 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</lang>
- 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
<lang apl>lcs ← ⌽+/∘(∧\)∘⊃∘(∧/2=/(⌊/≢¨)↑¨⌽¨)↑⌽∘⊃</lang>
- 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.
<lang applescript>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"}) --> ""</lang>
Functional
and for more productivity, and higher re-use of library functions, we can write a functional definition (rather than a procedure):
<lang applescript>------------------- 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</lang>
- Output:
['throne', 'sousaphone', 'tone'] -> 'one' ['prefix', 'suffix', 'infix'] -> 'fix' ['remark', 'spark', 'aardvark', 'lark'] -> 'ark' ['ectoplasm', 'banana', 'brick'] -> ''
AutoHotkey
<lang 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) }</lang> Examples:<lang AutoHotkey>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</lang>
- Output:
day throne cheese fix bar
AWK
<lang 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)
} </lang>
- 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
<lang 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$(""), "'"</lang>
- 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
<lang 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;
}</lang>
- Output:
[`baabababc` `baabc` `bbbabc` ] -> `abc` [`baabababc` `baabc` `bbbazc` ] -> `c` [`Sunday` `Monday` `Tuesday` `Wednesday` `Thursday` `Friday` `Saturday` ] -> `day` [`longest` `common` `suffix` ] -> `` [`suffix` ] -> `suffix` [`` ] -> ``
C++
<lang cpp>#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;
}</lang>
- 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
<lang 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);</lang>
- Output:
["baabababc", "baabc", "bbbabc"] -> `abc` ["baabababc", "baabc", "bbbazc"] -> `c` ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"] -> `day` ["longest", "common", "suffix"] -> `` [""] -> `` [] -> ``
D
<lang 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), '`'); }
}</lang>
- Output:
["baabababc", "baabc", "bbbabc"] -> `abc` ["baabababc", "baabc", "bbbazc"] -> `c` ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"] -> `day` ["longest", "common", "suffix"] -> `` ["suffix"] -> `suffix` [""] -> ``
Delphi
<lang Delphi> program Longest_common_suffix;
{$APPTYPE CONSOLE}
uses
System.SysUtils, Types;
type
TStringDynArrayHelper = record helper for TStringDynArray private class function Compare(const s: string; a: TStringDynArray; subSize: integer): Boolean; public function Reverse(value: string): string; function LongestSuffix: string; function Join(const sep: char): string; end;
{ TStringDynArrayHelper }
class function TStringDynArrayHelper.Compare(const s: string; a: TStringDynArray;
subSize: integer): Boolean;
var
i: Integer;
begin
for i := 0 to High(a) do if s <> a[i].Substring(0, subSize) then exit(False); Result := True;
end;
function TStringDynArrayHelper.Join(const sep: char): string; begin
Result := string.Join(sep, self);
end;
function TStringDynArrayHelper.LongestSuffix: string; var
ALength: Integer; i, lenMin, longest: Integer; ref: string;
begin
ALength := Length(self);
// Empty list if ALength = 0 then exit();
lenMin := MaxInt; for i := 0 to ALength - 1 do begin // One string is empty if self[i].IsEmpty then exit();
self[i] := Reverse(self[i]);
// Get the minimum length of string if lenMin > self[i].Length then lenMin := self[i].Length; end;
longest := -1; repeat inc(longest); ref := self[0].Substring(0, longest + 1); until not compare(ref, Self, longest + 1) or (longest >= lenMin);
Result := self[0].Substring(0, longest); Result := reverse(Result);
end;
function TStringDynArrayHelper.Reverse(value: string): string; var
ALength: Integer; i: Integer; c: Char;
begin
ALength := value.Length; Result := value;
if ALength < 2 then exit;
for i := 1 to ALength div 2 do begin c := Result[i]; Result[i] := Result[ALength - i + 1]; Result[ALength - i + 1] := c; end;
end;
var
List: TStringDynArray;
begin
List := ['baabababc', 'baabc', 'bbbabc'];
Writeln('Input:'); Writeln(List.Join(#10), #10); Writeln('Longest common suffix = ', List.LongestSuffix);
Readln;
end.
</lang>
- Output:
Input: baabababc baabc bbbabc Longest common suffix = abc
Factor
<lang factor>USING: accessors grouping kernel prettyprint sequences sequences.extras ;
! Like take-while, but for matrices and works from the rear.
- take-col-while-last ( ... matrix quot: ( ... col -- ... ? ) -- ... new-matrix )
[ [ <reversed> ] map flip ] dip take-while ; inline
- lcs ( seq -- lcs )
dup first swap [ all-equal? ] take-col-while-last to>> tail* ;
{ "baabababc" "baabc" "bbbabc" } lcs . { "baabababc" "baabc" "bbbazc" } lcs . { "" } lcs .</lang>
- Output:
"abc" "c" ""
FreeBASIC
<lang 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</lang>
- Output:
There are 3 words in the list: baabababc baabc bbbabc The longest common suffix is: abc
Go
<lang go>package main
import (
"fmt" "strings"
)
func lcs(a []string) string {
le := len(a) if le == 0 { return "" } if le == 1 { return a[0] } le0 := len(a[0]) minLen := le0 for i := 1; i < le; i++ { if len(a[i]) < minLen { minLen = len(a[i]) } } if minLen == 0 { return "" } res := "" a1 := a[1:] for i := 1; i <= minLen; i++ { suffix := a[0][le0-i:] for _, e := range a1 { if !strings.HasSuffix(e, suffix) { return res } } res = suffix } return res
}
func main() {
tests := [][]string{ {"baabababc", "baabc", "bbbabc"}, {"baabababc", "baabc", "bbbazc"}, {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}, {"longest", "common", "suffix"}, {"suffix"}, {""}, } for _, test := range tests { fmt.Printf("%v -> \"%s\"\n", test, lcs(test)) }
}</lang>
- Output:
[baabababc baabc bbbabc] -> "abc" [baabababc baabc bbbazc] -> "c" [Sunday Monday Tuesday Wednesday Thursday Friday Saturday] -> "day" [longest common suffix] -> "" [suffix] -> "suffix" [] -> ""
Haskell
This task clearly needs a little more work to bring it up to the usual standard – it's rather underspecified, and bereft of test samples – but one response, for the moment, might be something like: <lang haskell>import Data.List (transpose)
longestCommonSuffix :: [String] -> String longestCommonSuffix =
foldr (flip (<>) . return . head) [] . takeWhile (all =<< (==) . head) . transpose . fmap reverse
main :: IO () main =
mapM_ (putStrLn . longestCommonSuffix) [ [ "Sunday" , "Monday" , "Tuesday" , "Wednesday" , "Thursday" , "Friday" , "Saturday" ] , [ "Sondag" , "Maandag" , "Dinsdag" , "Woensdag" , "Donderdag" , "Vrydag" , "Saterdag" , "dag" ] ]</lang>
- Output:
day dag
J
<lang 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</lang>
- Output:
│baabababc│baabc│bbabc│ -> │abc│ │baabababc│baabc│bbazc│ -> │c│ │Sunday│Monday│Tuesday│Wednesday│Friday│Saturday│ -> │day│ │longest│common│suffix│ -> ││
Java
<lang 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)); } }
}</lang>
- Output:
[baabababc, baabc, bbbabc] -> `abc` [baabababc, baabc, bbbazc] -> `c` [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday] -> `day` [longest, common, suffix] -> `` [suffix] -> `suffix` [] -> ``
JavaScript
<lang 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();
})();</lang>
- 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. <lang jq>
- 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;</lang>
Test Cases <lang jq>def test:
["baabababc","baabc","bbbabc"], ["baabababc","baabc","bbbazc"], [""], [], ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"], ["throne","cone", "bone"] | "\(.) => \(longest_common_suffix)";
test </lang>
- Output:
["baabababc","baabc","bbbabc"] => abc ["baabababc","baabc","bbbazc"] => c [""] => [] => ["Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"] => day ["throne","cone","bone"] => one
Julia
<lang julia>function longestcommonsuffix(strings)
n, nmax = 0, minimum(length, strings) nmax == 0 && return "" while n <= nmax && all(s -> s[end-n] == strings[end][end-n], strings) n += 1 end return strings[1][end-n+1:end]
end
println(longestcommonsuffix(["baabababc","baabc","bbbabc"])) println(longestcommonsuffix(["baabababc","baabc","bbbazc"]))
println(longestcommonsuffix([""]))</lang>
- Output:
abc c
Kotlin
<lang scala>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)}`") }
}</lang>
- Output:
[baabababc, baabc, bbbabc] -> `abc` [baabababc, baabc, bbbazc] -> `c` [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday] -> `day` [longest, common, suffix] -> `` [suffix] -> `suffix` [] -> ``
Ksh
<lang 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
</lang>
- 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
<lang Mathematica>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"}]</lang>
- Output:
"one" "fix" "ark" "" "throne" "cheese" "" "" ""
Nim
<lang 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")</lang>
- 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. <lang perl>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)]}';
}</lang>
- Output:
'Sunday Monday Tuesday Wednesday Thursday Friday Saturday' ==> 'day' 'Sondag Maandag Dinsdag Woensdag Donderdag Vrydag Saterdag dag' ==> 'dag' '2347 9312347 acx5g2347 12.02347' ==> '2347' 'longest common suffix' ==> '' 'one, Hey! three, Hey! ale, Hey! me, Hey!' ==> 'e, Hey!' 'suffix' ==> 'suffix' '' ==> ''
Phix
Phix allows negative indexes, with -1 as the last element [same as $], and -length(s) the first element of s, so we can just do this:
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:
<lang python>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()</lang>
- Output:
day dag
Quackery
commonprefix
is defined at Longest common prefix#Quackery.
<lang Quackery> [ [] swap
witheach [ reverse nested join ] commonprefix reverse ] is commonsuffix ( [ --> $ )
$ "monday tuesday wednesday thursday friday saturday sunday" nest$ commonsuffix echo$</lang>
- Output:
day
Raku
<lang perl6>sub longest-common-suffix ( *@words ) {
return unless +@words; my $min = @words».chars.min; for 1 .. * { return @words[0].substr(* - $min) if $_ > $min; next if @words».substr(* - $_).Set == 1; return @words[0].substr(* - $_ + 1); }
}
say "{$_.raku} - LCS: >{longest-common-suffix $_}<" for
<Sunday Monday Tuesday Wednesday Thursday Friday Saturday>, <Sondag Maandag Dinsdag Woensdag Donderdag Vrydag Saterdag dag>, ( 2347, 9312347, 'acx5g2347', 12.02347 ), <longest common suffix>, ('one, Hey!', 'three, Hey!', 'ale, Hey!', 'me, Hey!'), 'suffix', </lang>
- Output:
("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday") - LCS: >day< ("Sondag", "Maandag", "Dinsdag", "Woensdag", "Donderdag", "Vrydag", "Saterdag", "dag") - LCS: >dag< (2347, 9312347, "acx5g2347", 12.02347) - LCS: >2347< ("longest", "common", "suffix") - LCS: >< ("one, Hey!", "three, Hey!", "ale, Hey!", "me, Hey!") - LCS: >e, Hey!< "suffix" - LCS: >suffix< "" - LCS: ><
REXX
Essentially, this REXX version simply reversed the strings, and then finds the longest common prefix. <lang rexx>/*REXX program finds the longest common suffix contained in an array of strings. */ parse arg z; z= space(z) /*obtain optional arguments from the CL*/ if z==|z=="," then z='baabababc baabc bbbabc' /*Not specified? Then use the default.*/ z= space(z); #= words(z) /*#: the number of words in the list. */ say 'There are ' # " words in the list: " z zr= reverse(z) /*reverse Z, find longest common prefix*/ @= word(zr, 1); m= length(@) /*get 1st word in reversed string; len.*/
do j=2 to #; x= word(zr, j) /*obtain a word (string) from the list.*/ t= compare(@, x) /*compare to the "base" word/string. */ if t==1 then do; @=; leave /*A mismatch of strings? Then leave, */ end /*no sense in comparing anymore strings*/ if t==0 & @==x then t= length(@) + 1 /*Both strings equal? Compute length. */ if t>=m then iterate /*T ≥ M? Then it's not longest string.*/ m= t - 1; @= left(@, max(0, m) ) /*redefine max length & the base string*/ end /*j*/
say /*stick a fork in it, we're all done. */ if m==0 then say 'There is no common suffix.'
else say 'The longest common suffix is: ' right( word(z, 1), m)</lang>
- output when using the default input:
There are 3 words in the list: baabababc baabc bbbabc The longest common suffix is: abc
Ring
<lang ring> load "stdlib.ring"
pre = ["baabababc","baabc","bbbabc"] len = len(pre) lenList = list(len) sub = list(len)
see "Input:" + nl see pre
for n = 1 to len
temp = pre[n] pre[n] = rever(temp)
next
for n = 1 to len
lenList[n] = len(pre[n])
next
lenList = sort(lenList) lenMax = lenList[1]
for m = 1 to lenMax
check = 0 sub1 = substr(pre[1],1,m) sub2 = substr(pre[2],1,m) sub3 = substr(pre[3],1,m) if sub1 = sub2 and sub2 = sub3 check = 1 ok if check = 1 longest = m ok
next
longPrefix = substr(pre[1],1,longest) longPrefix = rever(longPrefix)
see "Longest common suffix = " + longPrefix + nl
func rever(cstr)
cStr2 = "" for x = len(cStr) to 1 step -1 cStr2 = cStr2 + cStr[x] next return cStr2
</lang>
- Output:
Input: baabababc baabc bbbabc Longest common suffix = abc
Standard ML
<lang sml>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</lang>
Wren
<lang ecmascript>var lcs = Fn.new { |a|
if (a.count == 0) return "" if (a.count == 1) return a[0] var minLen = a.reduce(a[0].count) { |min, s| (s.count < min) ? s.count : min } if (minLen == 0) return "" var res = "" for (i in 1..minLen) { var suffix = a[0][-i..-1] for (e in a.skip(1)) { if (!e.endsWith(suffix)) return res } res = suffix } return res
}
var tests = [
["baabababc","baabc","bbbabc"], ["baabababc","baabc","bbbazc"], ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"], ["longest", "common", "suffix"], ["suffix"], [""]
] for (test in tests) System.print("%(test) -> \"%(lcs.call(test))\"")</lang>
- Output:
[baabababc, baabc, bbbabc] -> "abc" [baabababc, baabc, bbbazc] -> "c" [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday] -> "day" [longest, common, suffix] -> "" [suffix] -> "suffix" [] -> ""