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","interstelar","interstate") = "inters" lcp("throne","throne") = "throne" lcp("throne","dungeon") = lcp("cheese") = "cheese" lcp() = lcp() = lcp("prefix","suffix") =
Task inspired by this stackoverflow question: Find the longest common starting substring in a set of strings
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] } } 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", "interstelar", "interstate"}, {"throne", "throne"}, {"throne", "dungeon"}, {"cheese"}, {""}, nil, {"prefix", "suffix"}, } { fmt.Printf("lcp(%q) = %q\n", l, lcp(l)) } }</lang>
- Output:
lcp(["interspecies" "interstelar" "interstate"]) = "inters" lcp(["throne" "throne"]) = "throne" lcp(["throne" "dungeon"]) = "" lcp(["cheese"]) = "cheese" lcp([""]) = "" lcp([]) = "" lcp(["prefix" "suffix"]) = ""
Haskell
<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","interstelar","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"</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>
Perl 6
<lang perl6>multi lcp { } multi lcp(Str $s) { $s } multi lcp(*@s) {
first -> $s { [&&] map { m/^$s/ }, @s }, ( min(:by(*.chars), @s), *.chop ... * )
}
use Test; plan 7;
is lcp("interspecies","interstelar","interstate"), "inters"; is lcp("throne","throne"), "throne"; is lcp("throne","dungeon"), ; is lcp("cheese"), "cheese"; is lcp(), ; is lcp(), ; is lcp("prefix","suffix"), ;</lang>
- Output:
1..7 ok 1 - ok 2 - ok 3 - ok 4 - ok 5 - ok 6 - ok 7 -
PL/I
<lang pli>*process source xref attributes or(!);
(subrg): lcpt: Proc Options(main); Call assert(lcp('interspecies interstelar 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 interstelar 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","interstelar","interstate") == "inters" assert lcp("throne","throne") == "throne" assert lcp("throne","dungeon") == "" assert lcp("cheese") == "cheese" assert lcp("") == "" assert lcp("prefix","suffix") == ""</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","interstelar","interstate") == "inters" assert lcp("throne","throne") == "throne" assert lcp("throne","dungeon") == "" assert lcp("cheese") == "cheese" assert lcp("") == "" assert lcp("prefix","suffix") == ""</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>
REXX
<lang rexx>Call assert lcp("interspecies","interstelar","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'),"" 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","interstelar","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=""
Scala
<lang scala>class TestLCP extends FunSuite {
test("shared start") { assert(lcp("interspecies","interstelar","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>
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,interstelar,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,interstelar,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
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","interstelar","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)