Longest common prefix

Longest common prefix is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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:

$\forall x\ \in \ R:\ S\leq$_pref $\ x$ ~ "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, $\varepsilon$, is considered a prefix of all strings):

lcp("interspecies","interstelar","interstate") = "inters"
lcp("throne","throne") = "throne"
lcp("throne","dungeon") = $\varepsilon$
lcp("cheese") = "cheese"
lcp($\varepsilon$) = $\varepsilon$
lcp($\emptyset$) = $\varepsilon$
lcp("prefix","suffix") = $\varepsilon$

Task inspired by this stackoverflow question: Find the longest common starting substring in a set of strings

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>

Python

Python: Functional

To see if all the n'th characters are the same I sort and compare the first to the last in the lambda function. <lang python>from itertools import takewhile

def lcp(*s):

   return .join(ch[0] for ch in takewhile(lambda x: x.sort() or not x or x[0] == x[-1],

(list(y) for y in 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.

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>

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:

Translation of: Scala

<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)