Longest common prefix
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
See Also:
AutoHotkey
<lang AutoHotkey>lcp(str*){ for k, v in str w := v, list .= (list ? "`n" : "") v return RegExReplace(list, "^(.*)\K(\V*\R\1\V*)+$") }</lang> Examples:<lang AutoHotkey>MsgBox % lcp("interspecies","interstellar","interstate")</lang>
Outputs:
inters
C++
<lang Cpp>#include <set>
- include <algorithm>
- include <string>
- include <iostream>
- include <vector>
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>
- Output:
lcp("interspecies","interstellar","interstate") = inters
lcp( "throne" , "throne") = throne
lcp( "cheese" ) = cheese
lcp("") =
lcp( "prefix" , "suffix" ) =
lcp( "foo" , "foobar" ) = 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"
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>lcp :: (Eq a) => a -> [a] lcp = map head . takeWhile allEqual . truncTranspose where
-- similar to transpose, but stops on end of shortest list truncTranspose :: a -> a truncTranspose xs | any null xs = [] | otherwise = map head xs : truncTranspose (map tail xs) allEqual :: (Eq a) => [a] -> Bool allEqual (x:xs) = all (==x) xs
main = do
print $ lcp ["interspecies","interstellar","interstate"] -- prints "inters" print $ lcp ["throne","throne"] -- prints "throne" print $ lcp ["throne","dungeon"] -- prints "" print $ lcp ["cheese"] -- prints "cheese" print $ lcp [""] -- prints "" print $ lcp ["prefix","suffix"] -- prints "" print $ lcp ["foo","foobar"] -- prints "foo" print $ lcp ["abc" ++ repeat 'd',"abcde" ++ repeat 'f'] -- prints "abcd"</lang>
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 (well designed) handling of edge cases here.
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
ES 5
<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);
} : fnSeed = function (x) {
return [x];
});
}, null)
} else return [];
}</lang>
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>
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 Perl 6 example.
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 -
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=""
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>
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.
REXX
version 1
<lang 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 pgm computes the longest common prefix of any number of strings. */ say LCP('interspecies', "interstellar", 'interstate') say LCP('throne', "throne") /*two strings, exactly the same. */ say LCP('throne', "dungeon") /*2 completely different strings.*/ say LCP('throne', , "throne") /*3 strings, middle one is null. */ say LCP('cheese') /*just a single cheesy argument. */ say LCP() /*just a single null argument. */ say LCP() /*no arguments specified at all. */ say LCP('prefix', "suffix") /*two mostly different strings. */ say LCP('foo', "foobar") /*two mostly similar strings. */ say LCP('prefix', "suffix") /*two mostly different strings. */ say LCP('a', "b", 'c', "aaa") /*four strings, mostly different.*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────LCP subroutine──────────────────────*/ LCP: @=arg(1); m=length(@); a=arg(); say copies('▒',50)
do i=1 for a; say '────────────── string' i":" arg(i); end
do j=2 to a; 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 pgm computes the longest common prefix of any number of strings. */ say LCP('interspecies', "interstellar", 'interstate') say LCP('throne', "throne") /*two strings, exactly the same. */ say LCP('throne', "dungeon") /*2 completely different strings.*/ say LCP('throne', , "throne") /*3 strings, middle one is null. */ say LCP('cheese') /*just a single cheesy argument. */ say LCP() /*just a single null argument. */ say LCP() /*no arguments 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 done.*/ /*──────────────────────────────────LCP subroutine──────────────────────*/ LCP: @=arg(1); m=length(@); a=arg(); say copies('▒',60)
say '────────────── number of strings specified:' a do i=1 for a; say '────────────── string' i":" showNull(arg(i)); end
do j=2 to a; 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 subroutine─────────────────*/ 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»
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"
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 ((var keys = hash.keys).len == 1) {
return __FUNC__(hash{keys[0]}, acc+keys[0]);
}
return acc;
}
- Creates a tree like: {a => {b => {c => {}}}}
func lcp(*strings) {
var hash = Hash.new;
strings.sort_by{.len}.each { |str|
var ref = hash;
str.is_empty && return ;
str.each { |char|
if (ref.has_key(char)) {
ref = ref{char};
ref.keys.len == 0 && break;
} else {
ref = (ref{char} = Hash.new);
}
};
};
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"
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
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>
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)