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.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Given a set of strings, R, for a prefix S, it should hold that:
- pref
- (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
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> <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)