Longest common prefix: Difference between revisions
(add bash) |
(Added Quackery.) |
||
Line 2,660: | Line 2,660: | ||
[prefix, suffix] -> |
[prefix, suffix] -> |
||
[foo, foobar] -> foo</pre> |
[foo, foobar] -> foo</pre> |
||
=={{header|Quackery}}== |
|||
<lang> [ dup [] = iff |
|||
[ drop true ] done |
|||
true swap |
|||
behead swap |
|||
witheach |
|||
[ over != if |
|||
[ dip not conclude ] ] |
|||
drop ] is allsame ( [ --> b ) |
|||
[ dup [] = iff |
|||
[ drop 0 ] done |
|||
behead size swap |
|||
witheach [ size min ] ] is minsize ( [ --> n ) |
|||
[ over [] = iff |
|||
drop done |
|||
[] unrot |
|||
swap witheach |
|||
[ over split |
|||
drop nested |
|||
rot swap join swap ] |
|||
drop ] is truncall ( [ n --> ] ) |
|||
[ dup [] = if done |
|||
dup minsize truncall |
|||
[ dup allsame not while |
|||
-1 truncall |
|||
again ] |
|||
0 peek ] is commonprefix ( [ --> $ ) |
|||
[ dup $ "" = if |
|||
[ drop |
|||
$ "** empty string" ] |
|||
echo$ |
|||
cr ] is echoresult ( $ --> $ ) |
|||
$ "interspecies interstellar interstate" |
|||
nest$ commonprefix echoresult |
|||
$ "throne throne" |
|||
nest$ commonprefix echoresult |
|||
$ "throne throne" |
|||
nest$ $ "" swap 1 stuff |
|||
commonprefix echoresult |
|||
$ "throne dungeon" |
|||
nest$ commonprefix echoresult |
|||
$ "cheese" |
|||
nest$ commonprefix echoresult |
|||
$ "" |
|||
nest$ commonprefix echoresult |
|||
' [ ] commonprefix echoresult |
|||
$ "prefix suffix" |
|||
nest$ commonprefix echoresult |
|||
$ "foo foobar" |
|||
nest$ commonprefix echoresult</lang> |
|||
{{out}} |
|||
<pre>inters |
|||
throne |
|||
** empty string |
|||
** empty string |
|||
cheese |
|||
** empty string |
|||
** empty string |
|||
** empty string |
|||
foo |
|||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
Revision as of 09:46, 10 June 2021
It is often useful to find the common prefix of a set of strings, that is, the longest initial portion of all strings that are identical.
Given a set of strings, R, for a prefix S, it should hold that:
- pref ~ "for all members x of set R, it holds true that string S is a prefix of x"
- (help here: does not express that S is the longest common prefix of x)
An example use case for this: given a set of phone numbers, identify a common dialing code. This can be accomplished by first determining the common prefix (if any), and then matching it against know dialing codes (iteratively dropping characters from rhs until a match is found, as the lcp function may match more than the dialing code).
- Test cases
For a function, lcp, accepting a list of strings, the following should hold true (the empty string, , is considered a prefix of all strings):
lcp("interspecies","interstellar","interstate") = "inters" lcp("throne","throne") = "throne" lcp("throne","dungeon") = lcp("throne",,"throne") = lcp("cheese") = "cheese" lcp() = lcp() = lcp("prefix","suffix") = lcp("foo","foobar") = "foo"
Task inspired by this stackoverflow question: Find the longest common starting substring in a set 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 lcp(sa)
I sa.empty R ‘’ I sa.len == 1 R sa[0]
V min_len = min(sa.map(s -> s.len))
L(i) 0 .< min_len V p = sa[0][i] L(j) 1 .< sa.len I sa[j][i] != p R sa[0][0 .< i]
R sa[0][0 .< min_len]
F test(sa)
print(String(sa)‘ -> ’lcp(sa))
test([‘interspecies’, ‘interstellar’, ‘interstate’]) test([‘throne’, ‘throne’]) test([‘throne’, ‘dungeon’]) test([‘throne’, ‘’, ‘throne’]) test([‘cheese’]) test([‘’]) test([‘prefix’, ‘suffix’]) test([‘foo’, ‘foobar’])</lang>
- Output:
[interspecies, interstellar, interstate] -> inters [throne, throne] -> throne [throne, dungeon] -> [throne, , throne] -> [cheese] -> cheese [] -> [prefix, suffix] -> [foo, foobar] -> foo
Ada
<lang Ada>with Ada.Text_IO; with Ada.Strings.Unbounded;
procedure Longest_Prefix is
package Common_Prefix is procedure Reset; procedure Consider (Item : in String); function Prefix return String; end Common_Prefix;
package body Common_Prefix is use Ada.Strings.Unbounded; Common : Unbounded_String; Active : Boolean := False;
procedure Reset is begin Common := Null_Unbounded_String; Active := False; end Reset;
procedure Consider (Item : in String) is Len : constant Natural := Natural'Min (Length (Common), Item'Length); begin if not Active then Active := True; Common := To_Unbounded_String (Item); else for I in 1 .. Len loop if Element (Common, I) /= Item (Item'First + I - 1) then Head (Common, I - 1); return; end if; end loop; Head (Common, Len); end if; end Consider;
function Prefix return String is (To_String (Common));
end Common_Prefix;
use Common_Prefix;
begin
Consider ("interspecies"); Consider ("interstellar"); Consider ("interstate"); Ada.Text_IO.Put_Line (Prefix);
Reset; Consider ("throne"); Consider ("throne"); Ada.Text_IO.Put_Line (Prefix);
Reset; Consider ("throne"); Consider ("dungeon"); Ada.Text_IO.Put_Line (Prefix);
Reset; Consider ("prefix"); Consider ("suffix"); Ada.Text_IO.Put_Line (Prefix);
Reset; Consider ("foo"); Consider ("foobar"); Ada.Text_IO.Put_Line (Prefix);
Reset; Consider ("foo"); Ada.Text_IO.Put_Line (Prefix);
Reset; Consider (""); Ada.Text_IO.Put_Line (Prefix);
Reset; Ada.Text_IO.Put_Line (Prefix);
end Longest_Prefix;</lang>
Aime
<lang aime>lcp(...) {
integer n; record r; text l;
ucall(r_fix, 1, r, 0); n = 0; if (~r) { l = r.low; n = prefix(r.high, l); }
l.cut(0, n);
}
main(void) {
o_("\"", lcp("interspecies", "interstellar", "interstate"), "\"\n"); o_("\"", lcp("throne", "throne"), "\"\n"); o_("\"", lcp("throne", "dungeon"), "\"\n"); o_("\"", lcp("throne", "", "throne"), "\"\n"); o_("\"", lcp("cheese"), "\"\n"); o_("\"", lcp(""), "\"\n"); o_("\"", lcp(), "\"\n"); o_("\"", lcp("prefix", "suffix"), "\"\n"); o_("\"", lcp("foo", "foobar"), "\"\n");
0;
}</lang>
- Output:
"inters" "throne" "" "" "cheese" "" "" "" "foo"
ALGOL 68
<lang algol68># find the longest common prefix of two strings # PRIO COMMONPREFIX = 1; OP COMMONPREFIX = ( STRING a, b )STRING:
BEGIN INT a pos := LWB a; INT a max = UPB a; INT b pos := LWB b; INT b max = UPB b; WHILE IF a pos > a max OR b pos > b max THEN FALSE ELSE a[ a pos ] = b[ b pos ] FI DO a pos +:= 1; b pos +:= 1 OD; a[ LWB a : a pos - 1 ] END # COMMONPREFIX # ;
- get the length of a string #
OP LEN = ( STRING a )INT: ( UPB a + 1 ) - LWB a;
- find the longest common prefix of an array of STRINGs #
OP LONGESTPREFIX = ( []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 prefix := list[ LWB list ] COMMONPREFIX list[ 1 + LWB list ]; FOR pos FROM 2 + LWB list TO UPB list DO STRING next prefix := list[ pos ] COMMONPREFIX prefix; IF LEN next prefix < LEN prefix THEN # this element has a smaller common prefix # prefix := next prefix FI OD; prefix FI ;
- test the LONGESTPREFIX operator #
PROC test prefix = ( []STRING list, STRING expected result )VOID:
BEGIN STRING prefix = LONGESTPREFIX list; print( ( "longest common prefix of (" ) ); FOR pos FROM LWB list TO UPB list DO print( ( " """, list[ pos ], """" ) ) OD; print( ( " ) is: """, prefix, """ " , IF prefix = expected result THEN "as expected" ELSE "NOT AS EXPECTED" FI , newline ) ) END # test prefix # ;
[ 1 : 0 ]STRING empty list; # for recent versions of Algol 68G, can't just put "()" for an empty list #
BEGIN
test prefix( ( "interspecies", "interstellar", "interstate" ), "inters" ); test prefix( ( "throne", "throne" ), "throne" ); test prefix( ( "throne", "dungeon" ), "" ); test prefix( ( "throne", "", "throne" ), "" ); test prefix( ( "cheese" ), "cheese" ); test prefix( ( "" ), "" ); test prefix( empty list, "" ); test prefix( ( "prefix", "suffix" ), "" ); test prefix( ( "foo", "foobar" ), "foo" )
END</lang>
- Output:
longest common prefix of ( "interspecies" "interstellar" "interstate" ) is: "inters" as expected longest common prefix of ( "throne" "throne" ) is: "throne" as expected longest common prefix of ( "throne" "dungeon" ) is: "" as expected longest common prefix of ( "throne" "" "throne" ) is: "" as expected longest common prefix of ( "cheese" ) is: "cheese" as expected longest common prefix of ( "" ) is: "" as expected longest common prefix of ( ) is: "" as expected longest common prefix of ( "prefix" "suffix" ) is: "" as expected longest common prefix of ( "foo" "foobar" ) is: "foo" as expected
AppleScript
AppleScriptObjC
<lang applescript>use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later use framework "Foundation"
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: longestCommonPrefix({"interspecies", "interstellar", "interstate"}) --> "inters" longestCommonPrefix({"throne", "throne"}) --> "throne" longestCommonPrefix({"throne", "dungeon"}) --> "" longestCommonPrefix({"throne", "", "throne"}) --> "" longestCommonPrefix({""}) --> "" longestCommonPrefix({}) --> "" longestCommonPrefix({"prefix", "suffix"}) --> "" longestCommonPrefix({"foo", "foobar"}) --> "foo"</lang>
Functional
and for more productivity, and higher re-use of existing library functions, we can write a functional definition (rather than a procedure).
<lang applescript>------------------- LONGEST COMMON PREFIX ------------------
-- longestCommonPrefix :: [String] -> String
on longestCommonPrefix(xs)
if 1 < length of xs then map(my fst, ¬ takeWhile(my allSame, my transpose(xs))) as text else xs as text end if
end longestCommonPrefix
TESTS --------------------------
on run
script test on |λ|(xs) showList(xs) & " -> '" & longestCommonPrefix(xs) & "'" end |λ| end script unlines(map(test, {¬ {"interspecies", "interstellar", "interstate"}, ¬ {"throne", "throne"}, ¬ {"throne", "dungeon"}, ¬ {"throne", "", "throne"}, ¬ {"cheese"}, ¬ {""}, ¬ {}, ¬ {"prefix", "suffix"}, ¬ {"foo", "foobar"}}))
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
-- chars :: String -> [Char]
on chars(s)
characters of s
end chars
-- 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
-- eq (==) :: Eq a => a -> a -> Bool
on eq(a)
script on |λ|(b) a = b end |λ| end script
end eq
-- 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
-- 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:
['interspecies', 'interstellar', 'interstate'] -> 'inters' ['throne', 'throne'] -> 'throne' ['throne', 'dungeon'] -> '' ['throne', '', 'throne'] -> '' ['cheese'] -> 'cheese' [''] -> '' [] -> '' ['prefix', 'suffix'] -> '' ['foo', 'foobar'] -> 'foo'
Arturo
<lang rebol>lcp: function [lst][ ret: ""
idx: 0 while [true] [ thisLetter: "" loop lst 'word [ if idx=size word -> return ret if thisLetter="" -> thisLetter: get split word idx if thisLetter<>get split word idx -> return ret ] ret: ret ++ thisLetter idx: idx + 1 ]
]
print lcp ["interspecies" "interstellar" "interstate"] print lcp ["throne" "throne"] print lcp ["throne" "dungeon"] print lcp ["throne" "" "throne"] print lcp ["cheese"] print lcp [""] print lcp ["prefix" "suffix"] print lcp ["foo" "foobar"]</lang>
- Output:
inters throne cheese foo
AutoHotkey
<lang AutoHotkey>lcp(data){ for num, v in StrSplit(data.1) for i, word in data if (SubStr(word, 1, num) <> SubStr(data.1, 1, num)) return SubStr(word, 1, num-1) return SubStr(word, 1, num) }</lang> Examples:<lang AutoHotkey>MsgBox % "" . "`n" lcp(["interspecies","interstellar","interstate"]) . "`n" lcp(["throne","throne"]) . "`n" lcp(["throne","dungeon"]) . "`n" lcp(["throne","","throne"]) . "`n" lcp(["cheese"]) . "`n" lcp([""]) . "`n" lcp([]) . "`n" lcp(["prefix","suffix"]) . "`n" lcp(["foo","foobar"]) return</lang>
- Output:
inters throne cheese foo
AWK
<lang AWK>
- syntax: GAWK -f LONGEST_COMMON_PREFIX.AWK
BEGIN {
words_arr[++n] = "interspecies,interstellar,interstate" words_arr[++n] = "throne,throne" words_arr[++n] = "throne,dungeon" words_arr[++n] = "throne,,throne" words_arr[++n] = "cheese" words_arr[++n] = "" words_arr[++n] = "prefix,suffix" words_arr[++n] = "foo,foobar" for (i=1; i<=n; i++) { str = words_arr[i] printf("'%s' = '%s'\n",str,lcp(str)) } exit(0)
} function lcp(str, arr,hits,i,j,lcp_leng,n,sw_leng) {
n = split(str,arr,",") if (n == 0) { # null string return("") } if (n == 1) { # only 1 word, then it's the longest return(str) } sw_leng = length(arr[1]) for (i=2; i<=n; i++) { # find shortest word length if (length(arr[i]) < sw_leng) { sw_leng = length(arr[i]) } } for (i=1; i<=sw_leng; i++) { # find longest common prefix hits = 0 for (j=1; j<n; j++) { if (substr(arr[j],i,1) == substr(arr[j+1],i,1)) { hits++ } } if (hits == 0) { break } if (hits + 1 == n) { lcp_leng++ } } return(substr(str,1,lcp_leng))
} </lang>
Output:
'interspecies,interstellar,interstate' = 'inters' 'throne,throne' = 'throne' 'throne,dungeon' = '' 'throne,,throne' = '' 'cheese' = 'cheese' '' = '' 'prefix,suffix' = '' 'foo,foobar' = 'foo'
C
<lang C>
- include<stdarg.h>
- include<string.h>
- include<stdlib.h>
- include<stdio.h>
char* lcp(int num,...){ va_list vaList,vaList2; int i,j,len,min; char* dest; char** strings = (char**)malloc(num*sizeof(char*));
va_start(vaList,num); va_start(vaList2,num);
for(i=0;i<num;i++){ len = strlen(va_arg(vaList,char*)); strings[i] = (char*)malloc((len + 1)*sizeof(char));
strcpy(strings[i],va_arg(vaList2,char*));
if(i==0) min = len; else if(len<min) min = len; }
if(min==0) return "";
for(i=0;i<min;i++){ for(j=1;j<num;j++){ if(strings[j][i]!=strings[0][i]){ if(i==0) return ""; else{ dest = (char*)malloc(i*sizeof(char)); strncpy(dest,strings[0],i-1); return dest; } } } }
dest = (char*)malloc((min+1)*sizeof(char)); strncpy(dest,strings[0],min); return dest; }
int main(){
printf("\nLongest common prefix : %s",lcp(3,"interspecies","interstellar","interstate"));
printf("\nLongest common prefix : %s",lcp(2,"throne","throne")); printf("\nLongest common prefix : %s",lcp(2,"throne","dungeon")); printf("\nLongest common prefix : %s",lcp(3,"throne","","throne")); printf("\nLongest common prefix : %s",lcp(1,"cheese")); printf("\nLongest common prefix : %s",lcp(1,"")); printf("\nLongest common prefix : %s",lcp(0,NULL)); printf("\nLongest common prefix : %s",lcp(2,"prefix","suffix")); printf("\nLongest common prefix : %s",lcp(2,"foo","foobar"));
return 0; } </lang> Output:
Longest common prefix : inter Longest common prefix : throne Longest common prefix : Longest common prefix : Longest common prefix : cheese Longest common prefix : Longest common prefix : Longest common prefix : Longest common prefix : foo
C#
<lang csharp>using System;
namespace LCP {
class Program { public static string LongestCommonPrefix(params string[] sa) { if (null == sa) return ""; //special case string ret = ""; int idx = 0;
while (true) { char thisLetter = '\0'; foreach (var word in sa) { if (idx == word.Length) { // if we reached the end of a word then we are done return ret; } if (thisLetter == '\0') { // if this is the first word then note the letter we are looking for thisLetter = word[idx]; } if (thisLetter != word[idx]) { return ret; } }
// if we haven't said we are done then this position passed ret += thisLetter; idx++; } }
static void Main(string[] args) { Console.WriteLine(LongestCommonPrefix("interspecies", "interstellar", "interstate")); Console.WriteLine(LongestCommonPrefix("throne", "throne")); Console.WriteLine(LongestCommonPrefix("throne", "dungeon")); Console.WriteLine(LongestCommonPrefix("throne", "", "throne")); Console.WriteLine(LongestCommonPrefix("cheese")); Console.WriteLine(LongestCommonPrefix("")); Console.WriteLine(LongestCommonPrefix(null)); Console.WriteLine(LongestCommonPrefix("prefix", "suffix")); Console.WriteLine(LongestCommonPrefix("foo", "foobar")); } }
}</lang>
- Output:
inters throne cheese foo
C++
<lang Cpp>#include <set>
- include <algorithm>
- include <string>
- include <iostream>
- include <vector>
- include <numeric>
std::set<std::string> createPrefixes ( const std::string & s ) {
std::set<std::string> result ; for ( int i = 1 ; i < s.size( ) + 1 ; i++ ) result.insert( s.substr( 0 , i )) ; return result ;
}
std::set<std::string> findIntersection ( const std::set<std::string> & a ,
const std::set<std::string> & b ) { std::set<std::string> intersection ; std::set_intersection( a.begin( ) , a.end( ) , b.begin( ) , b.end( ) ,
std::inserter ( intersection , intersection.begin( ) ) ) ;
return intersection ;
}
std::set<std::string> findCommonPrefixes( const std::vector<std::string> & theStrings ) {
std::set<std::string> result ; if ( theStrings.size( ) == 1 ) { result.insert( *(theStrings.begin( ) ) ) ; } if ( theStrings.size( ) > 1 ) { std::vector<std::set<std::string>> prefixCollector ; for ( std::string s : theStrings )
prefixCollector.push_back( createPrefixes ( s ) ) ;
std::set<std::string> neutralElement (createPrefixes( *(theStrings.begin( ) ) )) ; result = std::accumulate( prefixCollector.begin( ) , prefixCollector.end( ) ,
neutralElement , findIntersection ) ;
} return result ;
}
std::string lcp( const std::vector<std::string> & allStrings ) {
if ( allStrings.size( ) == 0 ) return "" ; if ( allStrings.size( ) == 1 ) { return allStrings[ 0 ] ; } if ( allStrings.size( ) > 1 ) { std::set<std::string> prefixes( findCommonPrefixes ( allStrings ) ) ; if ( prefixes.empty( ) )
return "" ;
else {
std::vector<std::string> common ( prefixes.begin( ) , prefixes.end( ) ) ; std::sort( common.begin( ) , common.end( ) , [] ( const std::string & a, const std::string & b ) { return a.length( ) > b.length( ) ; } ) ; return *(common.begin( ) ) ;
} }
}
int main( ) {
std::vector<std::string> input { "interspecies" , "interstellar" , "interstate" } ; std::cout << "lcp(\"interspecies\",\"interstellar\",\"interstate\") = " << lcp ( input ) << std::endl ; input.clear( ) ; input.push_back( "throne" ) ; input.push_back ( "throne" ) ; std::cout << "lcp( \"throne\" , \"throne\"" << ") = " << lcp ( input ) << std::endl ; input.clear( ) ; input.push_back( "cheese" ) ; std::cout << "lcp( \"cheese\" ) = " << lcp ( input ) << std::endl ; input.clear( ) ; std::cout << "lcp(\"\") = " << lcp ( input ) << std::endl ; input.push_back( "prefix" ) ; input.push_back( "suffix" ) ; std::cout << "lcp( \"prefix\" , \"suffix\" ) = " << lcp ( input ) << std::endl ; input.clear( ) ; input.push_back( "foo" ) ; input.push_back( "foobar" ) ; std::cout << "lcp( \"foo\" , \"foobar\" ) = " << lcp ( input ) << std::endl ; return 0 ;
}</lang>
Another more concise version (C++14 for comparing dissimilar containers):
<lang cpp>
- include <algorithm>
- include <string>
- include <iostream>
- include <vector>
std::string lcp( const std::vector<std::string> & allStrings ) { if (allStrings.empty()) return std::string(); const std::string &s0 = allStrings.front(); auto end = s0.cend(); for(auto it=std::next(allStrings.cbegin()); it != allStrings.cend(); it++){ auto loc = std::mismatch(s0.cbegin(), s0.cend(), it->cbegin(), it->cend()); if (std::distance(loc.first, end)>0) end = loc.first; } return std::string(s0.cbegin(), end); }
int main( ) {
std::vector<std::string> input { "interspecies" , "interstellar" , "interstate" } ; std::cout << "lcp(\"interspecies\",\"interstellar\",\"interstate\") = " << lcp ( input ) << std::endl ; input.clear( ) ; input.push_back( "throne" ) ; input.push_back ( "throne" ) ; std::cout << "lcp( \"throne\" , \"throne\"" << ") = " << lcp ( input ) << std::endl ; input.clear( ) ; input.push_back( "cheese" ) ; std::cout << "lcp( \"cheese\" ) = " << lcp ( input ) << std::endl ; input.clear( ) ; std::cout << "lcp(\"\") = " << lcp ( input ) << std::endl ; input.push_back( "prefix" ) ; input.push_back( "suffix" ) ; std::cout << "lcp( \"prefix\" , \"suffix\" ) = " << lcp ( input ) << std::endl ; input.clear( ) ; input.push_back( "foo" ) ; input.push_back( "foobar" ) ; std::cout << "lcp( \"foo\" , \"foobar\" ) = " << lcp ( input ) << std::endl ; return 0 ;
} </lang>
- Output:
lcp("interspecies","interstellar","interstate") = inters lcp( "throne" , "throne") = throne lcp( "cheese" ) = cheese lcp("") = lcp( "prefix" , "suffix" ) = lcp( "foo" , "foobar" ) = foo
D
<lang D>import std.stdio;
string lcp(string[] list ...) {
string ret = ""; int idx;
while(true) { char thisLetter = 0; foreach (word; list) { if (idx == word.length) { return ret; } if(thisLetter == 0) { //if this is the first word then note the letter we are looking for thisLetter = word[idx]; } if (thisLetter != word[idx]) { //if this word doesn't match the letter at this position we are done return ret; } } ret ~= thisLetter; //if we haven't said we are done then this position passed idx++; }
}
void main() {
writeln(lcp("interspecies","interstellar","interstate")); writeln(lcp("throne","throne")); writeln(lcp("throne","dungeon")); writeln(lcp("throne","","throne")); writeln(lcp("cheese")); writeln(lcp("")); writeln(lcp("prefix","suffix")); writeln(lcp("foo","foobar"));
}</lang>
- Output:
inters throne cheese foo
Dyalect
<lang dyalect>func lcp(sa...) {
if sa.len() == 0 || !sa[0] { return "" }
var ret = "" var idx = 0
while true { var thisLetter = '\0' for word in sa { if idx == word.len() { return ret } if thisLetter == '\0' { thisLetter = word[idx] } if thisLetter != word[idx] { return ret } }
ret += thisLetter idx += 1 }
}
print(lcp("interspecies", "interstellar", "interstate")) print(lcp("throne", "throne")) print(lcp("throne", "dungeon")) print(lcp("throne", "", "throne")) print(lcp("cheese")) print(lcp("")) print(lcp(nil)) print(lcp("prefix", "suffix")) print(lcp("foo", "foobar"))</lang>
- Output:
inters throne cheese foo
EchoLisp
<lang lisp>
- find common prefix of two strings
(define (prefix s t ) (for/string ((u s) (v t)) #:break (not (= u v)) u))
(prefix "foo" "foobar") → "foo"
- fold over a list of strings
(define (lcp strings) (if (null? strings) "" (foldl prefix (first strings) (rest strings))))
define lcp-test '( ("interspecies" "interstellar" "interstate") ("throne" "throne") ("throne" "dungeon") ("cheese") ("") () ("prefix" "suffix")))
(for ((t lcp-test)) (writeln t '→ (lcp t)))
("interspecies" "interstellar" "interstate") → "inters" ("throne" "throne") → "throne" ("throne" "dungeon") → "" ("cheese") → "cheese" ("") → "" null → "" ("prefix" "suffix") → ""
</lang>
Elixir
<lang elixir>defmodule RC do
def lcp([]), do: "" def lcp(strs) do min = Enum.min(strs) max = Enum.max(strs) index = Enum.find_index(0..String.length(min), fn i -> String.at(min,i) != String.at(max,i) end) if index, do: String.slice(min, 0, index), else: min end
end
data = [
["interspecies","interstellar","interstate"], ["throne","throne"], ["throne","dungeon"], ["throne","","throne"], ["cheese"], [""], [], ["prefix","suffix"], ["foo","foobar"]
]
Enum.each(data, fn strs ->
IO.puts "lcp(#{inspect strs}) = #{inspect RC.lcp(strs)}"
end)</lang>
- Output:
lcp(["interspecies", "interstellar", "interstate"]) = "inters" lcp(["throne", "throne"]) = "throne" lcp(["throne", "dungeon"]) = "" lcp(["throne", "", "throne"]) = "" lcp(["cheese"]) = "cheese" lcp([""]) = "" lcp([]) = "" lcp(["prefix", "suffix"]) = "" lcp(["foo", "foobar"]) = "foo"
Erlang
A bow to the perversion of the Scala implementation. Not canonical erlang, this.
<lang erlang>
-module(lcp). -export([ main/1 ]).
shortest(List,Size) when length(List) =:= 0 ->
Size;
shortest(List,Size) ->
[H|T] = List, if length(H) < Size -> shortest(T, length(H) ); true -> shortest(T, Size )
end.
uniq(List, Size ) ->
First = string:substr(hd(List),1,Size), Last = string:substr(lists:last(List),1,Size), Ttuples = lists:zip(First, Last), % this is the bit that is like the scala version TheList = lists:takewhile( fun(E) -> case element(1,E) =:= element(2,E) of true -> true; _ -> false end end, Ttuples), Prefix = length(TheList), io:format("Prefix: ~p~n", [string:substr(First,1,Prefix)]).
main(List) ->
Sorted = lists:sort(List), if length(List) < 2 -> io:format("Prefix empty:$~p~n",[List]); true -> Size = length(hd(List)), uniq(Sorted, shortest(Sorted,Size)) end.
</lang>
- Output:
6> Data = [["interspecies","interstellar","interstate"], ["throne","throne"], ["throne","dungeon"], ["throne",[],"throne"], ["cheese"], [[]], [], ["prefix","suffix"], ["foo","foobar"], ["foreign","forsake","forget","forlorn","forgiven"]]. 7> [lcp:main(X) || X <- Data]. Prefix: "inters" Prefix: "throne" Prefix: [] Prefix: [] Prefix empty:$["cheese"] Prefix empty:$[[]] Prefix empty:$[] Prefix: [] Prefix: "foo" Prefix: "for" [ok,ok,ok,ok,ok,ok,ok,ok,ok,ok]
Factor
<lang factor>USING: continuations formatting fry kernel sequences strings ; IN: rosetta-code.lcp
! Find the longest common prefix of two strings.
- binary-lcp ( str1 str2 -- str3 )
[ SBUF" " clone ] 2dip '[ _ _ [ over = [ suffix! ] [ drop return ] if ] 2each ] with-return >string ;
! Reduce a sequence of strings using binary-lcp.
- lcp ( seq -- str )
[ "" ] [ dup first [ binary-lcp ] reduce ] if-empty ;
- lcp-demo ( -- )
{ { "interspecies" "interstellar" "interstate" } { "throne" "throne" } { "throne" "dungeon" } { "throne" "" "throne" } { "cheese" } { "" } { } { "prefix" "suffix" } { "foo" "foobar" } } [ dup lcp "%u lcp = %u\n" printf ] each ;
MAIN: lcp-demo</lang>
- Output:
{ "interspecies" "interstellar" "interstate" } lcp = "inters" { "throne" "throne" } lcp = "throne" { "throne" "dungeon" } lcp = "" { "throne" "" "throne" } lcp = "" { "cheese" } lcp = "cheese" { "" } lcp = "" { } lcp = "" { "prefix" "suffix" } lcp = "" { "foo" "foobar" } lcp = "foo"
FreeBASIC
<lang freebasic>' FB 1.05.0 Win64
Function lcp(s() As String) As String
Dim As Integer lb = LBound(s) Dim As Integer ub = UBound(s) Dim length As Integer = ub - lb + 1 If length = 0 Then Return "" empty array If length = 1 Then Return s(lb) only one element ' find length of smallest string Dim minLength As Integer = Len(s(lb)) For i As Integer = lb + 1 To ub If Len(s(i)) < minLength Then minLength = Len(s(i)) If minLength = 0 Then Return "" at least one string is empty Next Dim prefix As String Dim isCommon As Boolean Do prefix = Left(s(lb), minLength) isCommon = True For i As Integer = lb + 1 To ub If Left(s(i), minLength) <> prefix Then isCommon = False Exit For End If Next If isCommon Then Return prefix minLength -= 1 If minLength = 0 Then Return "" Loop
End Function
Dim s1(1 To 3) As String = {"interspecies","interstellar","interstate"}
Print "lcp(""interspecies"",""interstellar"",""interstate"") = """; lcp(s1()); """"
Dim s2(1 To 2) As String = {"throne", "throne"} Print "lcp(""throne"", ""throne"") = """; lcp(s2()); """"
Dim s3(1 To 2) As String = {"throne", "dungeon"} Print "lcp(""throne"", ""dungeon"") = """; lcp(s3()); """"
Dim s4(1 To 3) As String = {"throne", "", "dungeon"} Print "lcp(""throne"", """", ""dungeon"") = """; lcp(s4()); """"
Dim s5(1 To 1) As String = {"cheese"} Print "lcp(""cheese"") = """; lcp(s5()); """"
Dim s6(1 To 1) As String Print "lcp("""") = """; lcp(s6()); """"
Dim s7() As String Print "lcp() = """; lcp(s7()); """"
Dim s8(1 To 2) As String = {"prefix", "suffix"} Print "lcp(""prefix"", ""suffix"") = """; lcp(s8()); """"
Dim s9(1 To 2) As String = {"foo", "foobar"} Print "lcp(""foo"", ""foobar"") = """; lcp(s9()); """"
Print Print "Press any key to quit" Sleep</lang>
- Output:
lcp("interspecies","interstellar","interstate") = "inters" lcp("throne", "throne") = "throne" lcp("throne", "dungeon") = "" lcp("throne", "", "dungeon") = "" lcp("cheese") = "cheese" lcp("") = "" lcp() = "" lcp("prefix", "suffix") = "" lcp("foo", "foobar") = "foo"
Go
<lang go>package main
import "fmt"
// lcp finds the longest common prefix of the input strings. // It compares by bytes instead of runes (Unicode code points). // It's up to the caller to do Unicode normalization if desired // (e.g. see golang.org/x/text/unicode/norm). func lcp(l []string) string { // Special cases first switch len(l) { case 0: return "" case 1: return l[0] } // LCP of min and max (lexigraphically) // is the LCP of the whole set. min, max := l[0], l[0] for _, s := range l[1:] { switch { case s < min: min = s case s > max: max = s } } for i := 0; i < len(min) && i < len(max); i++ { if min[i] != max[i] { return min[:i] } } // In the case where lengths are not equal but all bytes // are equal, min is the answer ("foo" < "foobar"). return min }
// Normally something like this would be a TestLCP function in *_test.go // and use the testing package to report failures. func main() { for _, l := range [][]string{ {"interspecies", "interstellar", "interstate"}, {"throne", "throne"}, {"throne", "dungeon"}, {"throne", "", "throne"}, {"cheese"}, {""}, nil, {"prefix", "suffix"}, {"foo", "foobar"}, } { fmt.Printf("lcp(%q) = %q\n", l, lcp(l)) } }</lang>
- Output:
lcp(["interspecies" "interstellar" "interstate"]) = "inters" lcp(["throne" "throne"]) = "throne" lcp(["throne" "dungeon"]) = "" lcp(["throne" "" "throne"]) = "" lcp(["cheese"]) = "cheese" lcp([""]) = "" lcp([]) = "" lcp(["prefix" "suffix"]) = "" lcp(["foo" "foobar"]) = "foo"
Haskell
This even works on infinite strings (that have a finite longest common prefix), due to Haskell's laziness. <lang haskell>import Data.List (intercalate, transpose)
lcp :: (Eq a) => a -> [a] lcp = fmap head . takeWhile ((all . (==) . head) <*> tail) . transpose
main :: IO () main = do
putStrLn $ intercalate "\n" (showPrefix <$> [ ["interspecies", "interstellar", "interstate"] , ["throne", "throne"] , ["throne", "dungeon"] , ["cheese"] , [""] , ["prefix", "suffix"] , ["foo", "foobar"] ]) putStrLn [] print $ lcp ["abc" <> repeat 'd', "abcde" <> repeat 'f']
showPrefix :: [String] -> String showPrefix = ((<>) . (<> " -> ") . show) <*> (show . lcp)</lang>
- Output:
["interspecies","interstellar","interstate"] -> "inters" ["throne","throne"] -> "throne" ["throne","dungeon"] -> "" ["cheese"] -> "cheese" [""] -> "" ["prefix","suffix"] -> "" ["foo","foobar"] -> "foo" "abcd"
J
<lang J>lcp=: {. {.~ 0 i.~ [: */2 =/\ ]</lang>
In other words: compare adjacent strings pair-wise, combine results logically, find first mismatch in any of them, take that many characters from the first of the strings.
Note that we rely on J's handling of edge cases here. In other words: if we have only one string that falls out as the longest prefix, and if we have no strings the result is the empty string.
As the number of adjacent pairs is O(n) where n is the number of strings, this approach could be faster in the limit cases than sorting.
Examples:
<lang J> lcp 'interspecies','interstellar',:'interstate' inters
lcp 'throne',:'throne'
throne
lcp 'throne',:'dungeon'
lcp ,:'cheese'
cheese
lcp ,:
lcp 0 0$
lcp 'prefix',:'suffix'
</lang>
Java
<lang java5>public class LCP {
public static String lcp(String... list){ if(list == null) return "";//special case String ret = ""; int idx = 0;
while(true){ char thisLetter = 0; for(String word : list){ if(idx == word.length()){ //if we reached the end of a word then we are done return ret; } if(thisLetter == 0){ //if this is the first word then note the letter we are looking for thisLetter = word.charAt(idx); } if(thisLetter != word.charAt(idx)){ //if this word doesn't match the letter at this position we are done return ret; } } ret += thisLetter;//if we haven't said we are done then this position passed idx++; } } public static void main(String[] args){ System.out.println(lcp("interspecies","interstellar","interstate")); System.out.println(lcp("throne","throne")); System.out.println(lcp("throne","dungeon")); System.out.println(lcp("throne","","throne")); System.out.println(lcp("cheese")); System.out.println(lcp("")); System.out.println(lcp(null)); System.out.println(lcp("prefix","suffix")); System.out.println(lcp("foo","foobar")); }
}</lang>
- Output:
inters throne cheese foo
JavaScript
ES5
<lang JavaScript>(function () {
'use strict';
function lcp() { var lst = [].slice.call(arguments), n = lst.length ? takewhile(same, zip.apply(null, lst)).length : 0;
return n ? lst[0].substr(0, n) : ; }
// (a -> Bool) -> [a] -> [a] function takewhile(p, lst) { var x = lst.length ? lst[0] : null; return x !== null && p(x) ? [x].concat(takewhile(p, lst.slice(1))) : []; }
// Zip arbitrary number of lists (an imperative implementation) // a -> a function zip() { var lngLists = arguments.length, lngMin = Infinity, lstZip = [], arrTuple = [], lngLen, i, j;
for (i = lngLists; i--;) { lngLen = arguments[i].length; if (lngLen < lngMin) lngMin = lngLen; }
for (i = 0; i < lngMin; i++) { arrTuple = []; for (j = 0; j < lngLists; j++) { arrTuple.push(arguments[j][i]); } lstZip.push(arrTuple); } return lstZip; }
// [a] -> Bool function same(lst) { return (lst.reduce(function (a, x) { return a === x ? a : null; }, lst[0])) !== null; }
// TESTS
return [ lcp("interspecies", "interstellar", "interstate") === "inters", lcp("throne", "throne") === "throne", lcp("throne", "dungeon") === "", lcp("cheese") === "cheese", lcp("") === "", lcp("prefix", "suffix") === "", lcp("foo", "foobar") == "foo" ];
})();</lang>
- Output:
<lang JavaScript>[true, true, true, true, true, true, true]</lang>
We could also, of course, use a functional implementation of a zip for an arbitrary number of arguments (e.g. as below).
A good balance is often, however, to functionally compose primitive elements which are themselves iteratively implemented.
The functional composition facilitates refactoring, code reuse, and brisk development, while the imperative implementations can sometimes give significantly better performance in ES5, which does not optimise tail recursion. ( Tail call optimisation is, however, envisaged for ES6 - see https://kangax.github.io/compat-table/es6/ for progress towards its implementation ).
This functionally implemented zip is significantly slower than the iterative version used above:
<lang JavaScript>// Zip arbitrary number of lists (a functional implementation, this time) // Accepts arrays or strings, and returns a function zip() {
var args = [].slice.call(arguments), lngMin = args.reduce(function (a, x) { var n = x.length; return n < a ? n : a; }, Infinity);
if (lngMin) { return args.reduce(function (a, v) { return ( typeof v === 'string' ? v.split() : v ).slice(0, lngMin).map(a ? function (x, i) { return a[i].concat(x); } : function (x) { return [x]; }); }, null) } else return [];
}</lang>
ES6
<lang javascript>(() => {
'use strict';
// lcp :: (Eq a) => a -> [a] const lcp = xs => { const go = xs => xs.some(isNull) ? ( [] ) : cons( map(head, xs), go(map(tail, xs)) ); return concat(map( head, takeWhile( allSame, go(map(chars, xs)) ) )); };
// TEST ---------------------------------------------
// showPrefix :: [String] -> String const showPrefix = xs => concat([show(xs), ' --> ', show(lcp(xs))]);
// main :: IO () const main = () => { const strResults = unlines(map( showPrefix, [ ["interspecies", "interstellar", "interstate"], ["throne", "throne"], ["throne", "dungeon"], ["cheese"], [""], ["prefix", "suffix"], ["foo", "foobar"] ] )); return ( // console.log(strResults), strResults ); };
// GENERIC FUNCTIONS --------------------------------
// allSame :: [a] -> Bool const allSame = xs => 0 === xs.length || (() => { const x = xs[0]; return xs.every(y => x === y) })();
// chars :: String -> [Char] const chars = s => s.split();
// concat :: a -> [a] // concat :: [String] -> String const concat = xs => 0 < xs.length ? (() => { const unit = 'string' !== typeof xs[0] ? ( [] ) : ; return unit.concat.apply(unit, xs); })() : [];
// cons :: a -> [a] -> [a] const cons = (x, xs) => [x].concat(xs);
// head :: [a] -> a const head = xs => xs.length ? xs[0] : undefined;
// isNull :: [a] -> Bool // isNull :: String -> Bool const isNull = xs => Array.isArray(xs) || ('string' === typeof xs) ? ( 1 > xs.length ) : undefined;
// map :: (a -> b) -> [a] -> [b] const map = (f, xs) => (Array.isArray(xs) ? ( xs ) : xs.split()).map(f);
// show :: a -> String const show = JSON.stringify;
// tail :: [a] -> [a] const tail = xs => 0 < xs.length ? xs.slice(1) : [];
// takeWhile :: (a -> Bool) -> [a] -> [a] // takeWhile :: (Char -> Bool) -> String -> String const takeWhile = (p, xs) => { const lng = xs.length; return 0 < lng ? xs.slice( 0, until( i => lng === i || !p(xs[i]), i => 1 + i, 0 ) ) : []; };
// unlines :: [String] -> String const unlines = xs => xs.join('\n');
// until :: (a -> Bool) -> (a -> a) -> a -> a const until = (p, f, x) => { let v = x; while (!p(v)) v = f(v); return v; };
// MAIN --- return main();
})();</lang>
- Output:
["interspecies","interstellar","interstate"] --> "inters" ["throne","throne"] --> "throne" ["throne","dungeon"] --> [] ["cheese"] --> "cheese" [""] --> [] ["prefix","suffix"] --> [] ["foo","foobar"] --> "foo"
jq
See #Scala for a description of the approach used in this section. <lang jq># If your jq includes until/2
- then feel free to omit the following definition:
def until(cond; next):
def _until: if cond then . else (next|_until) end; _until;</lang>
<lang jq>def longest_common_prefix:
if length == 0 then "" # by convention elif length == 1 then .[0] # for speed else sort | if .[0] == "" then "" # for speed else .[0] as $first | .[length-1] as $last | ([$first, $last] | map(length) | min) as $n | 0 | until( . == $n or $first[.:.+1] != $last[.:.+1]; .+1) | $first[0:.] end end;</lang>
Test Cases <lang jq>def check(ans): longest_common_prefix == ans;
(["interspecies","interstellar","interstate"] | check("inters")) and (["throne","throne"] | check("throne")) and (["throne","dungeon"] | check("")) and (["throne", "", "throne"] | check("")) and (["cheese"] | check("cheese")) and ([""] | check("")) and ([] | check("")) and (["prefix","suffix"] | check("")) and (["foo","foobar"] | check("foo")) </lang>
- Output:
<lang sh>$ jq -n -f longest_common_prefix.jq true</lang>
Julia
<lang julia>function lcp(str::AbstractString...)
r = IOBuffer() str = [str...] if !isempty(str) i = 1 while all(i ≤ length(s) for s in str) && all(s == str[1][i] for s in getindex.(str, i)) print(r, str[1][i]) i += 1 end end return String(r)
end
@show lcp("interspecies", "interstellar", "interstate") @show lcp("throne","throne") @show lcp("throne","dungeon") @show lcp("throne", "", "throne") @show lcp("cheese") @show lcp("") @show lcp() @show lcp("prefix","suffix") @show lcp("foo","foobar")</lang>
- Output:
lcp("interspecies", "interstellar", "interstate") = "inters" lcp("throne", "throne") = "throne" lcp("throne", "dungeon") = "" lcp("throne", "", "throne") = "" lcp("cheese") = "cheese" lcp("") = "" lcp() = "" lcp("prefix", "suffix") = "" lcp("foo", "foobar") = "foo"
Kotlin
<lang scala>// version 1.0.6
fun lcp(vararg sa: String): String {
if (sa.isEmpty()) return "" if (sa.size == 1) return sa[0] val minLength = sa.map { it.length }.min()!! var oldPrefix = "" var newPrefix: String for (i in 1 .. minLength) { newPrefix = sa[0].substring(0, i) for (j in 1 until sa.size) if (!sa[j].startsWith(newPrefix)) return oldPrefix oldPrefix = newPrefix } return oldPrefix
}
fun main(args: Array<String>) {
println("The longest common prefixes of the following collections of strings are:\n") println("""["interspecies","interstellar","interstate"] = "${lcp("interspecies", "interstellar", "interstate")}"""") println("""["throne","throne"] = "${lcp("throne", "throne")}"""") println("""["throne","dungeon"] = "${lcp("throne", "dungeon")}"""") println("""["throne","","throne"] = "${lcp("throne", "", "throne")}"""") println("""["cheese"] = "${lcp("cheese")}"""") println("""[""] = "${lcp("")}"""") println("""[] = "${lcp()}"""") println("""["prefix","suffix"] = "${lcp("prefix", "suffix")}"""") println("""["foo","foobar"] = "${lcp("foo", "foobar")}"""")
}</lang>
- Output:
The longest common prefixes of the following collections of strings are: ["interspecies","interstellar","interstate"] = "inters" ["throne","throne"] = "throne" ["throne","dungeon"] = "" ["throne","","throne"] = "" ["cheese"] = "cheese" [""] = "" [] = "" ["prefix","suffix"] = "" ["foo","foobar"] = "foo"
Lobster
<lang Lobster>// lcp finds the longest common prefix of the input strings
def lcp(l):
// Special cases first let len = l.length if len == 0: return "" else: if len == 1: return l[0] // LCP of min and max (lexigraphically) is the LCP of the whole set var min, max = l[0], l[0] for(l) s, i: if i > 0: if s < min: min = s else: if s > max: max = s let slen = min(min.length, max.length) if slen == 0: return "" for(slen) i: if min[i] != max[i]: return min.substring(0, i) // In the case where lengths are not equal but all bytes // are equal, min is the answer ("foo" < "foobar") return min
for([["interspecies", "interstellar", "interstate"],
["throne", "throne"], ["throne", "dungeon"], ["throne", "", "throne"], ["cheese"], [""], [], ["prefix", "suffix"], ["foo", "foobar"]]): print("lcp" + _ + " = \"" + lcp(_) + "\"")</lang>
- Output:
lcp["interspecies", "interstellar", "interstate"] = "inters" lcp["throne", "throne"] = "throne" lcp["throne", "dungeon"] = "" lcp["throne", "", "throne"] = "" lcp["cheese"] = "cheese" lcp[""] = "" lcp[] = "" lcp["prefix", "suffix"] = "" lcp["foo", "foobar"] = "foo"
Lua
<lang Lua>function lcp (strList)
local shortest, prefix, first = math.huge, "" for _, str in pairs(strList) do if str:len() < shortest then shortest = str:len() end end for strPos = 1, shortest do if strList[1] then first = strList[1]:sub(strPos, strPos) else return prefix end for listPos = 2, #strList do if strList[listPos]:sub(strPos, strPos) ~= first then return prefix end end prefix = prefix .. first end return prefix
end
local testCases, pre = {
{"interspecies", "interstellar", "interstate"}, {"throne", "throne"}, {"throne", "dungeon"}, {"throne", "", "throne"}, {"cheese"}, {""}, {nil}, {"prefix", "suffix"}, {"foo", "foobar"}
} for _, stringList in pairs(testCases) do
pre = lcp(stringList) if pre == "" then print(string.char(238)) else print(pre) end
end</lang>
- Output:
inters throne ε ε cheese ε ε ε foo
Maple
<lang Maple>lcp := proc(arr) local A: if (arr = []) then return "": end if: A := sort(arr): return (A[1][1..(StringTools:-CommonPrefix(A[1],A[-1]))]): end proc:</lang> Test Cases <lang Maple>lcp(["interspecies","interstellar","interstate"]); lcp(["throne","throne"]); lcp(["throne","dungeon"]); lcp(["throne","","dungeon"]); lcp(["cheese"]); lcp([""]); lcp([]); lcp(["prefix","suffix"]); lcp(["foo","foobar"]);</lang>
- Output:
inters throne "" "" cheese "" "" "" foo
MATLAB / Octave
<lang Matlab> function lcp = longest_common_prefix(varargin) ca = char(varargin); ix = [any(ca~=ca(1,:),1),1]; lcp = ca(1,1:find(ix,1)-1); end
longest_common_prefix('aa', 'aa', 'aac') </lang>
- Output:
ans = aa
MiniScript
We find the shortest and longest strings (without sorting, which makes the code slightly longer but much more efficient), and then just compare those. <lang MiniScript>lcp = function(strList)
if not strList then return null // find the shortest and longest strings (without sorting!) shortest = strList[0] longest = strList[0] for s in strList if s.len < shortest.len then shortest = s if s.len > longest.len then longest = s end for if shortest.len < 1 then return "" // now find how much of the shortest matches the longest for i in range(0, shortest.len-1) if shortest[i] != longest[i] then return shortest[:i] end for return shortest
end function
print lcp(["interspecies","interstellar","interstate"]) print lcp(["throne","throne"]) print lcp(["throne","dungeon"]) print lcp(["throne", "", "throne"]) print lcp(["cheese"]) print lcp([]) print lcp(["foo","foobar"])</lang>
- Output:
inters throne cheese null foo
Modula-2
<lang modula2>MODULE LCP; FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
TYPE String = ARRAY[0..15] OF CHAR;
PROCEDURE Length(str : String) : CARDINAL; VAR len : CARDINAL; BEGIN
len := 0; WHILE str[len] # 0C DO INC(len) END; RETURN len
END Length;
PROCEDURE LongestCommonPrefix(params : ARRAY OF String) : String; VAR
ret : String; idx,widx : CARDINAL; thisLetter : CHAR;
BEGIN
ret := ""; idx := 0; LOOP thisLetter := 0C; FOR widx:=0 TO HIGH(params) DO IF idx = Length(params[widx]) THEN (* if we reached the end of a word then we are done *) RETURN ret END; IF thisLetter = 0C THEN (* if this is the first word then note the letter we are looking for *) thisLetter := params[widx][idx] END; IF thisLetter # params[widx][idx] THEN RETURN ret END END;
(* if we haven't said we are done then this position passed *) ret[idx] := thisLetter; INC(idx); ret[idx] := 0C END; RETURN ret
END LongestCommonPrefix;
(* Main *) TYPE
AS3 = ARRAY[0..2] OF String; AS2 = ARRAY[0..1] OF String; AS1 = ARRAY[0..0] OF String;
BEGIN
WriteString(LongestCommonPrefix(AS3{"interspecies", "interstellar", "interstate"})); WriteLn; WriteString(LongestCommonPrefix(AS2{"throne", "throne"})); WriteLn; WriteString(LongestCommonPrefix(AS2{"throne", "dungeon"})); WriteLn; WriteString(LongestCommonPrefix(AS3{"throne", "", "throne"})); WriteLn; WriteString(LongestCommonPrefix(AS1{"cheese"})); WriteLn; WriteString(LongestCommonPrefix(AS1{""})); WriteLn; WriteString(LongestCommonPrefix(AS2{"prefix", "suffix"})); WriteLn; WriteString(LongestCommonPrefix(AS2{"foo", "foobar"})); WriteLn;
ReadChar
END LCP.</lang>
- Output:
inters throne cheese foo
Ol
<lang scheme> (define (lcp . args)
(if (null? args) "" (let loop ((args (map string->list args)) (out #null)) (if (or (has? args #null) (not (apply = (map car args)))) (list->string (reverse out)) (loop (map cdr args) (cons (caar args) out))))))
(print "> " (lcp "interspecies" "interstellar" "interstate")) (print "> " (lcp "throne" "throne")) (print "> " (lcp "throne" "dungeon")) (print "> " (lcp "throne" "" "throne")) (print "> " (lcp "cheese")) (print "> " (lcp "")) (print "> " (lcp)) (print "> " (lcp "prefix" "suffix")) (print "> " (lcp "foo" "foobar")) </lang> {Out}
> inters > throne > > > cheese > > > > foo
ooRexx
<lang oorexx>Call assert lcp(.list~of("interspecies","interstellar","interstate")),"inters" Call assert lcp(.list~of("throne","throne")),"throne" Call assert lcp(.list~of("throne","dungeon")),"" Call assert lcp(.list~of("cheese")),"cheese" Call assert lcp(.list~of("","")) Call assert lcp(.list~of("prefix","suffix")),"" Call assert lcp(.list~of("a","b","c",'aaa')),"" Exit
assert:
If arg(1)==arg(2) Then tag='ok' Else tag='??' Say tag 'lcp="'arg(1)'"' Say Return
lcp: Use Arg l a=l~makearray() s=l~makearray()~makestring((LINE),',') say 'lcp('s')' an=a~dimension(1) If an=1 Then
Return a[1]
s=lcp2(a[1],a[2]) Do i=3 To an While s<>
s=lcp2(s,a[i]) End
Return s
lcp2: Do i=1 To min(length(arg(1)),length(arg(2)))
If substr(arg(1),i,1)<>substr(arg(2),i,1) Then Leave End
Return left(arg(1),i-1)</lang>
- Output:
lcp(interspecies,interstellar,interstate) ok lcp="inters" lcp(throne,throne) ok lcp="throne" lcp(throne,dungeon) ok lcp="" lcp(cheese) ok lcp="cheese" lcp(,) ok lcp="" lcp(prefix,suffix) ok lcp="" lcp(a,b,c,aaa) ok lcp=""
Perl
If the strings are known not to contain null-bytes, we can let the regex backtracking engine find the longest common prefix like this:
<lang perl>sub lcp {
(join("\0", @_) =~ /^ ([^\0]*) [^\0]* (?:\0 \1 [^\0]*)* $/sx)[0];
}</lang>
Testing: <lang perl>use Test::More; plan tests => 8;
is lcp("interspecies","interstellar","interstate"), "inters"; is lcp("throne","throne"), "throne"; is lcp("throne","dungeon"), ""; is lcp("cheese"), "cheese"; is lcp(""), ""; is lcp(), ""; is lcp("prefix","suffix"), ""; is lcp("foo","foobar"), "foo";</lang>
- Output:
As in the Raku example.
Phix
<lang Phix>function lcp(sequence strings) string res = ""
if length(strings) then res = strings[1] for i=2 to length(strings) do string si = strings[i] for j=1 to length(res) do if j>length(si) or res[j]!=si[j] then res = res[1..j-1] exit end if end for if length(res)=0 then exit end if end for end if return res
end function
constant tests = {{"interspecies", "interstellar", "interstate"},
{"throne", "throne"}, {"throne", "dungeon"}, {"throne", "", "throne"}, {"cheese"}, {""}, {}, {"prefix", "suffix"}, {"foo", "foobar"} }
for i=1 to length(tests) do
?lcp(tests[i])
end for</lang>
- Output:
"inters" "throne" "" "" "cheese" "" "" "" "foo"
PL/I
<lang pli>*process source xref attributes or(!);
(subrg): lcpt: Proc Options(main); Call assert(lcp('interspecies interstellar interstate'),'inters'); Call assert(lcp('throne throne'),'throne'); Call assert(lcp('throne dungeon'),); Call assert(lcp('cheese'),'cheese'); Call assert(lcp(' '),' '); Call assert(lcp('prefix suffix'),); Call assert(lcp('a b c aaa'),);
assert: Proc(result,expected); Dcl (result,expected) Char(*) Var; Dcl tag Char(2) Init('ok'); If result^=expected Then tag='??'; Put Edit(tag,' lcp="',result,'"',)(Skip,4(a)); End;
lcp: Proc(string) Returns(Char(50) Var); Dcl string Char(*); Dcl xstring Char(50) Var; Dcl bn Bin Fixed(31) Init(0); Dcl bp(20) Bin Fixed(31); Dcl s Char(50) Var; Dcl i Bin Fixed(31); xstring=string!!' '; Put Edit('"'!!string!!'"')(Skip,a); Do i=2 To length(xstring); If substr(xstring,i,1)=' ' Then Do; bn+=1; bp(bn)=i; End; End; If bn=1 Then Return(substr(string,1,bp(1)-1)); s=lcp2(substr(string,1,bp(1)-1),substr(string,bp(1)+1,bp(2)-bp(1))); Do i=3 To bn While(s^=); s=lcp2(s,substr(string,bp(i-1)+1,bp(i)-bp(i-1))); End; Return(s); End;
lcp2: Proc(u,v) Returns(Char(50) Var); Dcl (u,v) Char(*); Dcl s Char(50) Var; Dcl i Bin Fixed(31); Do i=1 To min(length(u),length(v)); If substr(u,i,1)^=substr(v,i,1) Then Leave; End; Return(left(u,i-1)); End;
End;</lang>
- Output:
"interspecies interstellar interstate" ok lcp="inters" "throne throne" ok lcp="throne" "throne dungeon" ok lcp="" "cheese" ok lcp="cheese" " " ok lcp=" " "prefix suffix" ok lcp="" "a b c aaa" ok lcp=""
PowerShell
<lang PowerShell> function lcp ($arr) {
if($arr){ $arr = $arr | sort {$_.length} | select -unique if(1 -lt $arr.count) { $lim, $i, $test = $arr[0].length, 0, $true while (($i -lt $lim) -and $test) { $test = ($arr | group {$_[$i]}).Name.Count -eq 1 if ($test) {$i += 1} } $arr[0].substring(0,$i) } else {$arr} } else{}
} function show($arr) {
function quote($str) {"`"$str`""} "lcp @($(($arr | foreach{quote $_}) -join ', ')) = $(lcp $arr)"
} show @("interspecies","interstellar","interstate") show @("throne","throne") show @("throne","dungeon") show @("throne", "","throne") show @("cheese") show @("") show @() show @("prefix","suffix") show @("foo","foobar") </lang> Output:
lcp @("interspecies", "interstellar", "interstate") = inters lcp @("throne", "throne") = throne lcp @("throne", "dungeon") = lcp @("throne", "", "throne") = lcp @("cheese") = cheese lcp @("") = lcp @() = lcp @("prefix", "suffix") = lcp @("foo", "foobar") = foo
Prolog
<lang prolog>common_prefix(String1, String2, Prefix):-
string_chars(String1, Chars1), string_chars(String2, Chars2), common_prefix1(Chars1, Chars2, Chars), string_chars(Prefix, Chars).
common_prefix1([], _, []):-!. common_prefix1(_, [], []):-!. common_prefix1([C1|_], [C2|_], []):-
C1 \= C2, !.
common_prefix1([C|Chars1], [C|Chars2], [C|Chars]):-
common_prefix1(Chars1, Chars2, Chars).
lcp([], ""):-!. lcp([String], String):-!. lcp(List, Prefix):-
min_member(Min, List), max_member(Max, List), common_prefix(Min, Max, Prefix).
test(Strings):-
lcp(Strings, Prefix), writef('lcp(%t) = %t\n', [Strings, Prefix]).
main:-
test(["interspecies", "interstellar", "interstate"]), test(["throne", "throne"]), test(["throne", "dungeon"]), test(["throne", "", "throne"]), test(["cheese"]), test([""]), test([]), test(["prefix", "suffix"]), test(["foo", "foobar"]).</lang>
- Output:
lcp(["interspecies","interstellar","interstate"]) = "inters" lcp(["throne","throne"]) = "throne" lcp(["throne","dungeon"]) = "" lcp(["throne","","throne"]) = "" lcp(["cheese"]) = "cheese" lcp([""]) = "" lcp([]) = "" lcp(["prefix","suffix"]) = "" lcp(["foo","foobar"]) = "foo"
Python
Note: this makes use of the error in os.path.commonprefix
where it computes the longest common prefix regardless of directory separators rather than finding the common directory path.
<lang python>import os.path
def lcp(*s):
return os.path.commonprefix(s)
assert lcp("interspecies","interstellar","interstate") == "inters" assert lcp("throne","throne") == "throne" assert lcp("throne","dungeon") == "" assert lcp("cheese") == "cheese" assert lcp("") == "" assert lcp("prefix","suffix") == "" assert lcp("foo","foobar") == "foo"</lang>
Python: Functional
To see if all the n'th characters are the same I compare the min and max characters in the lambda function.
<lang python>from itertools import takewhile
def lcp(*s):
return .join(ch[0] for ch in takewhile(lambda x: min(x) == max(x),
zip(*s)))
assert lcp("interspecies","interstellar","interstate") == "inters" assert lcp("throne","throne") == "throne" assert lcp("throne","dungeon") == "" assert lcp("cheese") == "cheese" assert lcp("") == "" assert lcp("prefix","suffix") == "" assert lcp("foo","foobar") == "foo"</lang>
The above runs without output.
- Alternative Functional
An alternative solution that takes advantage of the observation that the longest common prefix of a set of strings must be the same as the longest common prefix of the lexicographically minimal string and the lexicographically maximal string, since moving away lexicographically can only shorten the common prefix, never lengthening it. Finding the min and max could do a lot of unnecessary work though, if the strings are long and the common prefix is short. <lang python>from itertools import takewhile
def lcp(*s):
return .join(a for a,b in takewhile(lambda x: x[0] == x[1],
zip(min(s), max(s))))</lang>
Or, defined in terms of a generic transpose function:
<lang Python>from itertools import (takewhile)
- lcp :: [String] -> String
def lcp(xs):
return .join( x[0] for x in takewhile(allSame, transpose(xs)) )
- TEST --------------------------------------------------
- main :: IO ()
def main():
def showPrefix(xs): return .join( ['[' + ', '.join(xs), '] -> ', lcp(xs)] )
print (*list(map(showPrefix, [ ["interspecies", "interstellar", "interstate"], ["throne", "throne"], ["throne", "dungeon"], ["cheese"], [""], ["prefix", "suffix"], ["foo", "foobar"]])), sep='\n' )
- GENERIC FUNCTIONS -------------------------------------
- allSame :: [a] -> Bool
def allSame(xs):
if 0 < len(xs): x = xs[0] return all(map(lambda y: x == y, xs)) else: return True
def transpose(xs):
return map(list, zip(*xs))
- TEST ---
if __name__ == '__main__':
main()</lang>
- Output:
[interspecies, interstellar, interstate] -> inters [throne, throne] -> throne [throne, dungeon] -> [cheese] -> cheese [] -> [prefix, suffix] -> [foo, foobar] -> foo
Quackery
<lang> [ dup [] = iff
[ drop true ] done true swap behead swap witheach [ over != if [ dip not conclude ] ] drop ] is allsame ( [ --> b )
[ dup [] = iff [ drop 0 ] done behead size swap witheach [ size min ] ] is minsize ( [ --> n ) [ over [] = iff drop done [] unrot swap witheach [ over split drop nested rot swap join swap ] drop ] is truncall ( [ n --> ] )
[ dup [] = if done dup minsize truncall [ dup allsame not while -1 truncall again ] 0 peek ] is commonprefix ( [ --> $ )
[ dup $ "" = if [ drop $ "** empty string" ] echo$ cr ] is echoresult ( $ --> $ )
$ "interspecies interstellar interstate" nest$ commonprefix echoresult $ "throne throne" nest$ commonprefix echoresult $ "throne throne" nest$ $ "" swap 1 stuff commonprefix echoresult $ "throne dungeon" nest$ commonprefix echoresult $ "cheese" nest$ commonprefix echoresult $ "" nest$ commonprefix echoresult ' [ ] commonprefix echoresult $ "prefix suffix" nest$ commonprefix echoresult $ "foo foobar" nest$ commonprefix echoresult</lang>
- Output:
inters throne ** empty string ** empty string cheese ** empty string ** empty string ** empty string foo
Racket
Note that there are three cases to the match, because zip
needs at least one list, and char=?
needs at least 2 characters to compare.
<lang>#lang racket (require srfi/1)
(define ε "") (define lcp
(match-lambda* [(list) ε] [(list a) a] [ss (list->string (reverse (let/ec k (fold (lambda (a d) (if (apply char=? a) (cons (car a) d) (k d))) null (apply zip (map string->list ss))))))]))
(module+ test
(require tests/eli-tester) (test (lcp "interspecies" "interstellar" "interstate") => "inters" (lcp "throne" "throne") => "throne" (lcp "throne" "dungeon") => "" (lcp "cheese") => "cheese" (lcp ε) => ε (lcp) => ε (lcp "prefix" "suffix") => ε))</lang>
All tests pass.
Raku
(formerly Perl 6)
This should work on infinite strings (if and when we get them), since .ords is lazy. In any case, it does just about the minimal work by evaluating all strings lazily in parallel. A few explanations of the juicy bits: @s is the list of strings, and the hyper operator » applies the .ords to each of those strings, producing a list of lists. The | operator inserts each of those sublists as an argument into an argument list so that we can use a reduction operator across the list of lists, which makes sense if the operator in question knows how to deal with list arguments. In this case we use the Z ('zip') metaoperator with eqv as a base operator, which runs eqv across all the lists in parallel for each position, and will fail if not all the lists have the same ordinal value at that position, or if any of the strings run out of characters. Then we count up the leading matching positions and carve up one of the strings to that length. <lang perl6>multi lcp() { } multi lcp($s) { ~$s } multi lcp(*@s) { substr @s[0], 0, [+] [\and] [Zeqv] |@s».ords }
use Test; plan 8;
is lcp("interspecies","interstellar","interstate"), "inters"; is lcp("throne","throne"), "throne"; is lcp("throne","dungeon"), ; is lcp("cheese"), "cheese"; is lcp(), ; is lcp(), ; is lcp("prefix","suffix"), ; is lcp("foo","foobar"), 'foo';</lang>
- Output:
1..8 ok 1 - ok 2 - ok 3 - ok 4 - ok 5 - ok 6 - ok 7 - ok 8 -
REXX
version 1
<lang rexx>/* REXX */ Call assert lcp("interspecies","interstellar","interstate"),"inters" Call assert lcp("throne","throne"),"throne" Call assert lcp("throne","dungeon"),"" Call assert lcp("cheese"),"cheese" Call assert lcp("","") Call assert lcp("prefix","suffix"),"" Call assert lcp("a","b","c",'aaa'),"" Call assert lcp("foo",'foobar'),"foo" Call assert lcp("ab","","abc"),"" Exit
assert:
If arg(1)==arg(2) Then tag='ok' Else tag='??' Say tag 'lcp="'arg(1)'"' Say Return
lcp: Procedure ol='test lcp(' Do i=1 To arg()
ol=ol||""""arg(i)"""" If i<arg() Then ol=ol',' Else ol=ol')' End
Say ol If arg()=1 Then
Return arg(1)
s=lcp2(arg(1),arg(2)) Do i=3 To arg() While s<>
s=lcp2(s,arg(i)) End
Return s
lcp2: Procedure Do i=1 To min(length(arg(1)),length(arg(2)))
If substr(arg(1),i,1)<>substr(arg(2),i,1) Then Leave End
Return left(arg(1),i-1)</lang>
- Output:
test lcp("interspecies","interstellar","interstate") ok lcp="inters" test lcp("throne","throne") ok lcp="throne" test lcp("throne","dungeon") ok lcp="" test lcp("cheese") ok lcp="cheese" test lcp("","") ok lcp="" test lcp("prefix","suffix") ok lcp="" test lcp("a","b","c","aaa") ok lcp=""
test lcp("foo","foobar") ok lcp="foo"
test lcp("ab","","abc") ok lcp=""
version 2
This REXX version makes use of the compare BIF. <lang rexx>/*REXX program computes the longest common prefix (LCP) of any number of strings.*/ say LCP('interspecies', "interstellar", 'interstate') say LCP('throne', "throne") /*2 strings, they are exactly the same.*/ say LCP('throne', "dungeon") /*2 completely different strings. */ say LCP('throne', , "throne") /*3 strings, the middle string is null.*/ say LCP('cheese') /*just a single cheesy argument. */ say LCP() /*just a single null argument. */ say LCP() /*no arguments are specified at all. */ say LCP('prefix', "suffix") /*two mostly different strings. */ say LCP('foo', "foobar") /*two mostly similar strings. */ say LCP('a', "b", 'c', "aaa") /*four strings, mostly different. */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ LCP: @= arg(1); m= length(@); #= arg(); say copies('▒', 50)
do i=1 for #; say '────────────── string' i":" arg(i) end /*i*/ do j=2 to #; x= arg(j); t= compare(@, x) /*compare to next.*/ if t==1 | x== then do; @= ; leave; end /*mismatch of strs*/ if t==0 & @==x then t= length(@) + 1 /*both are equal. */ if t>=m then iterate /*not longest str.*/ m= t - 1; @= left(@, max(0, m) ) /*define maximum. */ end /*j*/ return ' longest common prefix=' @ /*return answer. */</lang>
- output when using the default inputs:
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: interspecies ────────────── string 2: interstellar ────────────── string 3: interstate longest common prefix= inters ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: throne ────────────── string 2: throne longest common prefix= throne ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: throne ────────────── string 2: dungeon longest common prefix= ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: throne ────────────── string 2: ────────────── string 3: throne longest common prefix= ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: cheese longest common prefix= cheese ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: longest common prefix= ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ longest common prefix= ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: prefix ────────────── string 2: suffix longest common prefix= ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: foo ────────────── string 2: foobar longest common prefix= foo ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── string 1: a ────────────── string 2: b ────────────── string 3: c ────────────── string 4: aaa longest common prefix=
version 3
This REXX version explicitly shows null values and the number of strings specified. <lang rexx>/*REXX program computes the longest common prefix (LCP) of any number of strings.*/ say LCP('interspecies', "interstellar", 'interstate') say LCP('throne', "throne") /*2 strings, they are exactly the same.*/ say LCP('throne', "dungeon") /*2 completely different strings. */ say LCP('throne', , "throne") /*3 strings, the middle string is null.*/ say LCP('cheese') /*just a single cheesy argument. */ say LCP() /*just a single null argument. */ say LCP() /*no arguments are specified at all. */ say LCP('prefix', "suffix") /*two mostly different strings. */ say LCP('foo', "foobar") /*two mostly similar strings. */ say LCP('a', "b", 'c', "aaa") /*four strings, mostly different. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ LCP: @= arg(1); m= length(@); #=arg(); say copies('▒', 60)
say '────────────── number of strings specified:' # do i=1 for #; say '────────────── string' i":" showNull(arg(i)) end /*i*/
do j=2 to #; x= arg(j); t= compare(@, x) /*compare to next.*/ if t==1 | x== then do; @=; leave; end /*mismatch of strs*/ if t==0 & @==x then t= length(@) + 1 /*both are equal. */ if t>=m then iterate /*not longest str.*/ m= t - 1; @= left(@, max(0, m) ) /*define maximum. */ end /*j*/ return ' longest common prefix=' shownull(@) /*return answer. */
/*──────────────────────────────────────────────────────────────────────────────────────*/ showNull: procedure; parse arg z; if z== then z= "«null»"; return z</lang>
- output when using the default inputs:
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 3 ────────────── string 1: interspecies ────────────── string 2: interstellar ────────────── string 3: interstate longest common prefix= inters ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 2 ────────────── string 1: throne ────────────── string 2: throne longest common prefix= throne ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 2 ────────────── string 1: throne ────────────── string 2: dungeon longest common prefix= «null» ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 3 ────────────── string 1: throne ────────────── string 2: «null» ────────────── string 3: throne longest common prefix= «null» ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 1 ────────────── string 1: cheese longest common prefix= cheese ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 1 ────────────── string 1: «null» longest common prefix= «null» ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 0 longest common prefix= «null» ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 2 ────────────── string 1: prefix ────────────── string 2: suffix longest common prefix= «null» ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 2 ────────────── string 1: foo ────────────── string 2: foobar longest common prefix= foo ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ ────────────── number of strings specified: 4 ────────────── string 1: a ────────────── string 2: b ────────────── string 3: c ────────────── string 4: aaa longest common prefix= «null»
Ring
<lang ring>
- Project : Longest common prefix
aList1 = ["interspecies","interstellar","interstate"] aList2 = list(len(aList1)) flag = 1 comp="" for n=1 to len(aList1[1])
aList2 = list(len(aList1)) flag=1 for m=1 to len(aList1) aList2[m] = left(aList1[m], n ) compare = left(aList1[1], n ) next for p=1 to len(aList1) if aList2[p] != compare flag = 0 exit ok next if flag=1 if len(compare) > comp comp=compare ok ok
next if comp=""
see "none"
else
see comp + nl
ok </lang> Output:
inters
Ruby
<lang ruby>def lcp(*strs)
return "" if strs.empty? min, max = strs.minmax idx = min.size.times{|i| break i if min[i] != max[i]} min[0...idx]
end
data = [
["interspecies","interstellar","interstate"], ["throne","throne"], ["throne","dungeon"], ["throne","","throne"], ["cheese"], [""], [], ["prefix","suffix"], ["foo","foobar"]
]
data.each do |set|
puts "lcp(#{set.inspect[1..-2]}) = #{lcp(*set).inspect}"
end</lang>
- Output:
lcp("interspecies", "interstellar", "interstate") = "inters" lcp("throne", "throne") = "throne" lcp("throne", "dungeon") = "" lcp("throne", "", "throne") = "" lcp("cheese") = "cheese" lcp("") = "" lcp() = "" lcp("prefix", "suffix") = "" lcp("foo", "foobar") = "foo"
Rust
Rust String by default is utf-8 encoded. Since utf-8 is variable width, indexing in constant time is not possible. This example therefore uses byte strings (slices of u8) for the strings. The implementation shown here is similar to the Java implementation.
<lang Rust> fn main() {
let strs: [&[&[u8]]; 7] = [ &[b"interspecies", b"interstellar", b"interstate"], &[b"throne", b"throne"], &[b"throne", b"dungeon"], &[b"cheese"], &[b""], &[b"prefix", b"suffix"], &[b"foo", b"foobar"], ]; strs.iter().for_each(|list| match lcp(list) { Some(prefix) => println!("{}", String::from_utf8_lossy(&prefix)), None => println!(), });
}
fn lcp(list: &[&[u8]]) -> Option<Vec<u8>> {
if list.is_empty() { return None; } let mut ret = Vec::new(); let mut i = 0; loop { let mut c = None; for word in list { if i == word.len() { return Some(ret); } match c { None => { c = Some(word[i]); } Some(letter) if letter != word[i] => return Some(ret), _ => continue, } } if let Some(letter) = c { ret.push(letter); } i += 1; }
} </lang>
Output:
inters throne cheese foo
Scala
Take the first and last of the set of sorted strings; zip the two strings into a sequence of tuples ('view' makes this happen laziliy, on demand), until the two characters in the tuple differ, at which point, unzip the sequence into two character sequences; finally, arbitarily take one of these sequences (they are identical) and convert back to a string
"interspecies" \ / i, n, t, e, r, s \ > zip takeWhile: (i,i), (n,n), (t,t), (e,e), (r,r), (s,s) unzip < > "inters" "intesteller" / \ i, n, t, e, r, s
<lang scala>class TestLCP extends FunSuite {
test("shared start") { assert(lcp("interspecies","interstellar","interstate") === "inters") assert(lcp("throne","throne") === "throne") assert(lcp("throne","dungeon").isEmpty) assert(lcp("cheese") === "cheese") assert(lcp("").isEmpty) assert(lcp(Nil :_*).isEmpty) assert(lcp("prefix","suffix").isEmpty) }
def lcp(list: String*) = list.foldLeft("")((_,_) => (list.min.view,list.max.view).zipped.takeWhile(v => v._1 == v._2).unzip._1.mkString)
}</lang>
Sidef
<lang ruby># Finds the first point where the tree bifurcates func find_common_prefix(hash, acc) {
if (hash.len == 1) { var pair = hash.to_a[0] return __FUNC__(pair.value, acc+pair.key) } return acc
}
- Creates a tree like: {a => {b => {c => {}}}}
func lcp(*strings) {
var hash = Hash()
for str in (strings.sort_by{.len}) { var ref = hash str.is_empty && return for char in str { if (ref.contains(char)) { ref = ref{char} ref.len == 0 && break } else { ref = (ref{char} = Hash()) } } }
return find_common_prefix(hash, )
}</lang>
Demonstration: <lang ruby>var data = [
["interspecies","interstellar","interstate"], ["throne","throne"], ["throne","dungeon"], ["throne","","throne"], ["cheese"], [""], [], ["prefix","suffix"], ["foo","foobar"]
];
data.each { |set|
say "lcp(#{set.dump.substr(1,-1)}) = #{lcp(set...).dump}";
};</lang>
- Output:
lcp("interspecies", "interstellar", "interstate") = "inters" lcp("throne", "throne") = "throne" lcp("throne", "dungeon") = "" lcp("throne", "", "throne") = "" lcp("cheese") = "cheese" lcp("") = "" lcp() = "" lcp("prefix", "suffix") = "" lcp("foo", "foobar") = "foo"
Smalltalk
There is already a longestCommonPrefix method in Collection; however, if there wasn't, the following will do: <lang smalltalk>prefixLength := [:a :b |
|end| end := (a size) min:(b size). ((1 to:end) detect:[:i | (a at:i) ~= (b at:i)] ifNone:end+1)-1].
lcp := [:words |
words isEmpty ifTrue:[] ifFalse:[ |first l| first := words first. l := (words from:2) inject:first size into:[:minSofar :w | minSofar min:(prefixLength value:first value:w)]. first copyTo:l]].
- (
('interspecies' 'interstellar' 'interstate') ('throne' 'throne') ('throne' 'dungeon') ('throne' 'throne') ('cheese') () () ('prefix' 'suffix') ('foo' 'foobar')
) do:[:eachList |
Transcript show:eachList storeString; show:' ==> '; showCR:(lcp value:eachList)
]</lang>
- Output:
#('interspecies' 'interstellar' 'interstate') ==> inters #('throne' 'throne') ==> throne #('throne' 'dungeon') ==> #('throne' '' 'throne') ==> #('cheese') ==> cheese #('') ==> #() ==> #('prefix' 'suffix') ==> #('foo' 'foobar') ==> foo
Standard ML
<lang sml>val lcp =
let val longerFirst = fn pair as (a, b) => if size a < size b then (b, a) else pair and commonPrefix = fn (l, s) => case CharVector.findi (fn (i, c) => c <> String.sub (l, i)) s of SOME (i, _) => String.substring (s, 0, i) | _ => s in fn [] => "" | x :: xs => foldl (commonPrefix o longerFirst) x xs end</lang>
- Test:
<lang sml>val test = [
["interspecies", "interstellar", "interstate"], ["throne", "throne"], ["throne", "dungeon"], ["throne", "", "throne"], ["cheese"], [""], [], ["prefix", "suffix"], ["foo", "foobar"]
]
val () = (print o concat o map (fn lst => "'" ^ lcp lst ^ "'\n")) test</lang>
- Output:
'inters' 'throne' '' '' 'cheese' '' '' '' 'foo'
Swift
<lang swift>func commonPrefix(string1: String, string2: String) -> String {
return String(zip(string1, string2).prefix(while: {$0 == $1}).map{$0.0})
}
func longestCommonPrefix(_ strings: [String]) -> String {
switch (strings.count) { case 0: return "" case 1: return strings[0] default: return commonPrefix(string1: strings.min()!, string2: strings.max()!) }
}
func printLongestCommonPrefix(_ strings: [String]) {
print("lcp(\(strings)) = \"\(longestCommonPrefix(strings))\"")
}
printLongestCommonPrefix(["interspecies", "interstellar", "interstate"]) printLongestCommonPrefix(["throne", "throne"]) printLongestCommonPrefix(["throne", "dungeon"]) printLongestCommonPrefix(["throne", "", "throne"]) printLongestCommonPrefix(["cheese"]) printLongestCommonPrefix([""]) printLongestCommonPrefix([]) printLongestCommonPrefix(["prefix", "suffix"]) printLongestCommonPrefix(["foo", "foobar"])</lang>
- Output:
lcp(["interspecies", "interstellar", "interstate"]) = "inters" lcp(["throne", "throne"]) = "throne" lcp(["throne", "dungeon"]) = "" lcp(["throne", "", "throne"]) = "" lcp(["cheese"]) = "cheese" lcp([""]) = "" lcp([]) = "" lcp(["prefix", "suffix"]) = "" lcp(["foo", "foobar"]) = "foo"
Tcl
Since TIP#195 this has been present as a core command:
<lang Tcl>% namespace import ::tcl::prefix % prefix longest {interstellar interspecies interstate integer} "" inte </lang>
UNIX Shell
<lang bash>#!/bin/bash
lcp () { local i=0 word c longest
case $# in 0) return 1 ;; 1) printf %s "$1" return ;; esac
while :; do c= for word; do [[ $i == ${#word} ]] && break 2 -z $c && c="${word:i:1}" [[ ${word:i:1} != "$c" ]] && break 2 done longest+="$c" ((i++)) done
printf %s "$longest" }
mapfile -t tests <<'TEST' interspecies interstellar interstate throne throne throne dungeon throne throne cheese
prefix suffix foo foobar TEST
for test in "${tests[@]}"; do mapfile -t -d $'\t' words <<<"$test" words=("${words[@]%$'\n'}") printf '%s -> "%s"\n' "$(declare -p words)" "$(lcp "${words[@]}")" done </lang>
- Output:
declare -a words=([0]="throne" [1]="throne") -> "throne" declare -a words=([0]="throne" [1]="dungeon") -> "" declare -a words=([0]="throne" [1]="" [2]="throne") -> "" declare -a words=([0]="cheese") -> "cheese" declare -a words=() -> "" declare -a words=([0]="prefix" [1]="suffix") -> "" declare -a words=([0]="foo" [1]="foobar") -> "foo"
VBScript
<lang vb>Function lcp(s) 'declare an array str = Split(s,",") 'indentify the length of the shortest word in the array For i = 0 To UBound(str) If i = 0 Then l = Len(str(i)) ElseIf Len(str(i)) < l Then l = Len(str(i)) End If Next 'check prefixes and increment index idx = 0 For j = 1 To l For k = 0 To UBound(str) If UBound(str) = 0 Then idx = Len(str(0)) Else If k = 0 Then tstr = Mid(str(k),j,1) ElseIf k <> UBound(str) Then If Mid(str(k),j,1) <> tstr Then Exit For End If Else If Mid(str(k),j,1) <> tstr Then Exit For Else idx = idx + 1 End If End If End If Next If idx = 0 Then Exit For End If Next 'return lcp If idx = 0 Then lcp = "No Matching Prefix" Else lcp = Mid(str(0),1,idx) End If End Function
'Calling the function for test cases. test = Array("interspecies,interstellar,interstate","throne,throne","throne,dungeon","cheese",_ "","prefix,suffix")
For n = 0 To UBound(test) WScript.StdOut.Write "Test case " & n & " " & test(n) & " = " & lcp(test(n)) WScript.StdOut.WriteLine Next</lang>
- Output:
Test case 0 interspecies,interstellar,interstate = inters Test case 1 throne,throne = throne Test case 2 throne,dungeon = No Matching Prefix Test case 3 cheese = cheese Test case 4 = No Matching Prefix Test case 5 prefix,suffix = No Matching Prefix
Visual Basic .NET
<lang vbnet>Module Module1
Function LongestCommonPrefix(ParamArray sa() As String) As String If IsNothing(sa) Then Return "" REM special case End If Dim ret = "" Dim idx = 0
While True Dim thisLetter = Nothing For Each word In sa If idx = word.Length Then REM if we reach the end of a word then we are done Return ret End If If IsNothing(thisLetter) Then REM if this is the first word, thennote the letter we are looking for thisLetter = word(idx) End If If thisLetter <> word(idx) Then Return ret End If Next
REM if we haven't said we are done the this position passed ret += thisLetter idx += 1 End While
Return "" End Function
Sub Main() Console.WriteLine(LongestCommonPrefix("interspecies", "interstellar", "interstate")) Console.WriteLine(LongestCommonPrefix("throne", "throne")) Console.WriteLine(LongestCommonPrefix("throne", "dungeon")) Console.WriteLine(LongestCommonPrefix("throne", "", "throne")) Console.WriteLine(LongestCommonPrefix("cheese")) Console.WriteLine(LongestCommonPrefix("")) Console.WriteLine(LongestCommonPrefix(Nothing)) Console.WriteLine(LongestCommonPrefix("prefix", "suffix")) Console.WriteLine(LongestCommonPrefix("foo", "foobar")) End Sub
End Module</lang>
- Output:
inters throne cheese foo
Wren
<lang ecmascript>import "/fmt" for Fmt
var lcp = Fn.new { |sa|
var size = sa.count if (size == 0) return "" if (size == 1) return sa[0] var minLen = sa.skip(1).reduce(sa[0].count) { |min, s| s.count < min ? s.count : min } var oldPrefix = "" for (i in 1..minLen) { var newPrefix = sa[0][0...i] for (j in 1...size) if (!sa[j].startsWith(newPrefix)) return oldPrefix oldPrefix = newPrefix } return oldPrefix
}
var lists = [
["interspecies","interstellar","interstate"], ["throne","throne"], ["throne","dungeon"], ["throne","","throne"], ["cheese"], [""], [], ["prefix","suffix"], ["foo","foobar"]
]
System.print("The longest common prefixes of the following collections of strings are:\n") for (sa in lists) {
Fmt.print(" $-46s = $q", Fmt.v("q", 0, sa), lcp.call(sa))
}</lang>
- Output:
The longest common prefixes of the following collections of strings are: ["interspecies", "interstellar", "interstate"] = "inters" ["throne", "throne"] = "throne" ["throne", "dungeon"] = "" ["throne", "", "throne"] = "" ["cheese"] = "cheese" [""] = "" [] = "" ["prefix", "suffix"] = "" ["foo", "foobar"] = "foo"
XProfan
<lang XProfan>Proc lcp
Parameters long liste Declare int longest, j, L, string s,t var int cnt = GetCount(liste) WhileLoop 0, cnt-1 L = Len(GetString$(liste,&loop)) case &loop == 0 : longest = L case L < longest : longest = L EndWhile s = GetString$(liste,0) WhileLoop 1, cnt-1 t = GetString$(liste,&loop) For j,1,longest If SubStr$(s,j) <> SubStr$(t,j) longest = j - 1 BREAK EndIf EndFor If longest < 1 Clear longest BREAK EndIf s = t EndWhile Return Left$(s,longest)
EndProc
cls declare string s[7] s[0] = "interspecies,interstellar,interstate" s[1] = "throne,throne" s[2] = "throne,dungeon" s[3] = "throne,,throne" s[4] = "cheese" s[5] = "" s[6] = "prefix,suffix" s[7] = "foo,foobar"
WhileLoop 0,7
ClearList 0 Move("StrToList",s[&loop],",") Print "list: ("+s[&loop]+") = "+chr$(34) + lcp(0) + chr$(34)
EndWhile
ClearList 0 WaitKey end</lang>
- Output:
list: (interspecies,interstellar,interstate) = "inters" list: (throne,throne) = "throne" list: (throne,dungeon) = "" list: (throne,,throne) = "" list: (cheese) = "cheese" list: () = "" list: (prefix,suffix) = "" list: (foo,foobar) = "foo"
zkl
The string method prefix returns the number of common prefix characters. <lang zkl>fcn lcp(s,strings){ s[0,s.prefix(vm.pasteArgs(1))] }</lang> Or, without using prefix:
<lang zkl>fcn lcp(strings){
vm.arglist.reduce(fcn(prefix,s){ Utils.Helpers.zipW(prefix,s) // lazy zip .pump(String,fcn([(a,b)]){ a==b and a or Void.Stop }) })
}</lang> <lang zkl>tester:=TheVault.Test.UnitTester.UnitTester(); tester.testRun(lcp.fp("interspecies","interstellar","interstate"),Void,"inters",__LINE__); tester.testRun(lcp.fp("throne","throne"),Void,"throne",__LINE__); tester.testRun(lcp.fp("throne","dungeon"),Void,"",__LINE__); tester.testRun(lcp.fp("cheese"),Void,"cheese",__LINE__); tester.testRun(lcp.fp(""),Void,"",__LINE__); tester.testRun(lcp.fp("prefix","suffix"),Void,"",__LINE__); tester.stats();</lang> The fp (partial application) method is used to delay running lcp until the tester actually tests.
- Output:
===================== Unit Test 1 ===================== Test 1 passed! ===================== Unit Test 2 ===================== Test 2 passed! ===================== Unit Test 3 ===================== Test 3 passed! ===================== Unit Test 4 ===================== Test 4 passed! ===================== Unit Test 5 ===================== Test 5 passed! ===================== Unit Test 6 ===================== Test 6 passed! 6 tests completed. Passed test(s): 6 (of 6)
- Draft Programming Tasks
- 11l
- Ada
- Aime
- ALGOL 68
- AppleScript
- Arturo
- AutoHotkey
- AWK
- C
- C sharp
- C++
- D
- Dyalect
- EchoLisp
- Elixir
- Erlang
- Factor
- FreeBASIC
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lobster
- Lua
- Maple
- MATLAB
- Octave
- MiniScript
- Modula-2
- Ol
- Perl
- Phix
- PL/I
- PowerShell
- Prolog
- Python
- Quackery
- Racket
- Raku
- REXX
- Ring
- Ruby
- Rust
- Scala
- Sidef
- Smalltalk
- Standard ML
- Swift
- Tcl
- UNIX Shell
- VBScript
- Visual Basic .NET
- Wren
- Wren-fmt
- XProfan
- Zkl