Longest common prefix: Difference between revisions

 

=={{header|11l}}==

I sa.empty

R ‘’

test([‘’])

test([‘prefix’, ‘suffix’])

 

{{out}}

[prefix, suffix] ->

[foo, foobar] -> foo

</pre>

 

=={{header|Ada}}==

with Ada.Strings.Unbounded;

 

Ada.Text_IO.Put_Line (Prefix);

 

 

=={{header|Aime}}==

{

integer n;

 

0;

{{Out}}

<pre>"inters"

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}

PRIO COMMONPREFIX = 1;

OP COMMONPREFIX = ( STRING a, b )STRING:

test prefix( ( "prefix", "suffix" ), "" );

test prefix( ( "foo", "foobar" ), "foo" )

{{out}}

<pre>

=={{header|AppleScript}}==

===AppleScriptObjC===

use framework "Foundation"

 

longestCommonPrefix({}) --> ""

longestCommonPrefix({"prefix", "suffix"}) --> ""

----

===Functional===

and for more productivity, and higher re-use of existing library functions, we can write a functional definition (rather than a procedure).

 

 

 

set my text item delimiters to dlm

str

{{Out}}

<pre>['interspecies', 'interstellar', 'interstate'] -> 'inters'

 

=={{header|Arturo}}==

ret: ""

idx: 0

print lcp [""]

print lcp ["prefix" "suffix"]

 

{{out}}

 

=={{header|AutoHotkey}}==

for num, v in StrSplit(data.1)

for i, word in data

return SubStr(word, 1, num-1)

return SubStr(word, 1, num)

. "`n" lcp(["interspecies","interstellar","interstate"])

. "`n" lcp(["throne","throne"])

. "`n" lcp(["prefix","suffix"])

. "`n" lcp(["foo","foobar"])

{{out}}

<pre>

 

=={{header|AWK}}==

# syntax: GAWK -f LONGEST_COMMON_PREFIX.AWK

BEGIN {

return(substr(str,1,lcp_leng))

}

<p>Output:</p>

<pre>

 

=={{header|C}}==

#include<stdarg.h>

#include<string.h>

return 0;

}

Output:

<pre>

=={{header|C sharp|C#}}==

{{trans|Java}}

 

namespace LCP {

}

}

{{out}}

<pre>inters

 

=={{header|C++}}==

#include <algorithm>

#include <string>

std::cout << "lcp( \"foo\" , \"foobar\" ) = " << lcp ( input ) << std::endl ;

return 0 ;

 

Another more concise version (C++14 for comparing dissimilar containers):

 

#include <algorithm>

#include <string>

return 0 ;

}

{{out}}

<pre>

lcp( "foo" , "foobar" ) = foo

</pre>

 

=={{header|D}}==

{{trans|Java}}

 

string lcp(string[] list ...) {

writeln(lcp("prefix","suffix"));

writeln(lcp("foo","foobar"));

{{out}}

<pre>inters

{{trans|C#}}

 

return ""

}

var ret = ""

var idx = 0

while true {

var thisLetter = '\0'

for word in sa {

return ret

}

}

}

ret += thisLetter

idx += 1

}

}

print(lcp("interspecies", "interstellar", "interstate"))

print(lcp("throne", "throne"))

print(lcp(nil))

print(lcp("prefix", "suffix"))

 

{{out}}

 

foo</pre>

 

=={{header|EchoLisp}}==

;; find common prefix of two strings

(define (prefix s t ) (for/string ((u s) (v t)) #:break (not (= u v)) u))

("prefix" "suffix") → ""

 

 

=={{header|Elixir}}==

end

 

 

{{out}}

<pre>

</pre>

 

=={{header|Erlang}}==

-module(lcp).

 

 

 

 

{{out}}

<pre>

</pre>

 

=={{header|Factor}}==

IN: rosetta-code.lcp

 

} [ dup lcp "%u lcp = %u\n" printf ] each ;

 

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

 

Function lcp(s() As String) As String

Print

Print "Press any key to quit"

 

{{out}}

 

=={{header|Go}}==

 

import "fmt"

fmt.Printf("lcp(%q) = %q\n", l, lcp(l))

}

{{out}}

<pre>

=={{header|Haskell}}==

This even works on infinite strings (that have a finite longest common prefix), due to Haskell's laziness.

 

lcp :: (Eq a) => [[a]] -> [a]

 

showPrefix :: [String] -> String

{{Out}}

<pre>["interspecies","interstellar","interstate"] -> "inters"

=={{header|J}}==

 

 

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.

Examples:

 

inters

lcp 'throne',:'throne'

 

lcp 'prefix',:'suffix'

 

=={{header|Java}}==

{{works with|Java|1.5+}}

public static String lcp(String... list){

if(list == null) return "";//special case

System.out.println(lcp("foo","foobar"));

}

{{out}}

<pre>inters

===ES5===

 

'use strict';

 

];

 

 

{{Out}}

 

 

 

This functionally implemented zip is significantly slower than the iterative version used above:

 

// Accepts arrays or strings, and returns [[a]]

function zip() {

}, null)

} else return [];

 

===ES6===

 

// lcp :: (Eq a) => [[a]] -> [a]

const lcp = xs => {

[]

);

)

};

 

 

 

// showPrefix :: [String] -> String

const showPrefix = xs =>

 

 

 

// allSame :: [a] -> Bool

const allSame = xs =>

})();

 

 

// head :: [a] -> a

 

// isNull :: [a] -> Bool

// isNull :: String -> Bool

const isNull = xs =>

 

 

// show :: a -> String

const show = JSON.stringify;

 

// tail :: [a] -> [a]

 

// takeWhile :: (a -> Bool) -> [a] -> [a]

 

 

 

// MAIN ---

return main();

{{Out}}

 

=={{header|jq}}==

 

See [[#Scala]] for a description of the approach used in this section.

# then feel free to omit the following definition:

def until(cond; next):

 

if length == 0 then "" # by convention

elif length == 1 then .[0] # for speed

| $first[0:.]

end

 

'''Test Cases'''

 

(["interspecies","interstellar","interstate"] | check("inters")) and

(["prefix","suffix"] | check("")) and

(["foo","foobar"] | check("foo"))

{{out}}

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

 

r = IOBuffer()

str = [str...]

@show lcp()

@show lcp("prefix","suffix")

 

{{out}}

 

=={{header|Kotlin}}==

 

fun lcp(vararg sa: String): String {

println("""["prefix","suffix"] = "${lcp("prefix", "suffix")}"""")

println("""["foo","foobar"] = "${lcp("foo", "foobar")}"""")

 

{{out}}

=={{header|Lobster}}==

{{trans|Go}}

 

def lcp(l):

["prefix", "suffix"],

["foo", "foobar"]]):

{{out}}

<pre>lcp["interspecies", "interstellar", "interstate"] = "inters"

 

=={{header|Lua}}==

local shortest, prefix, first = math.huge, ""

for _, str in pairs(strList) do

pre = lcp(stringList)

if pre == "" then print(string.char(238)) else print(pre) end

{{out}}

<pre>inters

 

=={{header|Maple}}==

local A:

if (arr = []) then return "": end if:

A := sort(arr):

return (A[1][1..(StringTools:-CommonPrefix(A[1],A[-1]))]):

'''Test Cases'''

lcp(["throne","throne"]);

lcp(["throne","dungeon"]);

lcp([]);

lcp(["prefix","suffix"]);

{{out}}

<pre>inters

""

foo</pre>

 

=={{header|MATLAB}} / {{header|Octave}}==

function lcp = longest_common_prefix(varargin)

ca = char(varargin);

 

longest_common_prefix('aa', 'aa', 'aac')

 

{{out}}

=={{header|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.

if not strList then return null

// find the shortest and longest strings (without sorting!)

print lcp(["cheese"])

print lcp([])

 

{{out}}

null

foo</pre>

 

=={{header|Modula-2}}==

{{trans|C#}}

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

 

 

ReadChar

{{out}}

<pre>inters

 

foo</pre>

 

=={{header|Ol}}==

(define (lcp . args)

(if (null? args)

(print "> " (lcp "prefix" "suffix"))

(print "> " (lcp "foo" "foobar"))

{Out}

<pre>

==ooRexx==

{{trans|REXX}}

Call assert lcp(.list~of("throne","throne")),"throne"

Call assert lcp(.list~of("throne","dungeon")),""

Leave

End

{{out}}

<pre>lcp(interspecies,interstellar,interstate)

If the strings are known not to contain null-bytes, we can let the regex backtracking engine find the longest common prefix like this:

 

(join("\0", @_) =~ /^ ([^\0]*) [^\0]* (?:\0 \1 [^\0]*)* $/sx)[0];

 

Testing:

plan tests => 8;

 

is lcp(), "";

is lcp("prefix","suffix"), "";

 

{{out}}

 

=={{header|Phix}}==

{{out}}

<pre>

=={{header|PL/I}}==

{{trans|REXX}}

(subrg):

lcpt: Proc Options(main);

End;

 

{{out}}

<pre>"interspecies interstellar interstate"

 

=={{header|PowerShell}}==

function lcp ($arr) {

if($arr){

show @("prefix","suffix")

show @("foo","foobar")

<b>Output:</b>

<pre>

=={{header|Prolog}}==

{{works with|SWI Prolog}}

string_chars(String1, Chars1),

string_chars(String2, Chars2),

test([]),

test(["prefix", "suffix"]),

 

{{out}}

Note: this makes use of the error in <code>os.path.commonprefix</code> where it computes the longest common prefix regardless of directory separators rather than [[Find common directory path#Python|finding the common directory path]].

 

 

def lcp(*s):

assert lcp("") == ""

assert lcp("prefix","suffix") == ""

 

===Python: Functional===

To see if all the n'th characters are the same I compare the min and max characters in the lambda function.

 

 

def lcp(*s):

assert lcp("") == ""

assert lcp("prefix","suffix") == ""

 

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.

 

def lcp(*s):

return ''.join(a for a,b in takewhile(lambda x: x[0] == x[1],

 

 

Or, defined in terms of a generic '''transpose''' function:

 

 

# TEST ---

if __name__ == '__main__':

{{Out}}

<pre>[interspecies, interstellar, interstate] -> inters

[prefix, suffix] ->

[foo, foobar] -> foo</pre>

 

=={{header|Racket}}==

Note that there are three cases to the match, because <code>zip</code> needs at least one list, and <code>char=?</code> needs at least 2 characters to compare.

 

(require srfi/1)

 

(lcp ε) => ε

(lcp) => ε

 

All tests pass.

{{works with|rakudo|2015-11-28}}

This should work on infinite strings (if and when we get them), since <tt>.ords</tt> 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: <tt>@s</tt> is the list of strings, and the hyper operator <tt>»</tt> applies the <tt>.ords</tt> to each of those strings, producing a list of lists. The <tt>|</tt> 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 <tt>Z</tt> ('zip') metaoperator with <tt>eqv</tt> as a base operator, which runs <tt>eqv</tt> 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.

multi lcp($s) { ~$s }

multi lcp(*@s) { substr @s[0], 0, [+] [\and] [Zeqv] |@s».ords }

is lcp(), '';

is lcp("prefix","suffix"), '';

{{out}}

<pre>1..8

=={{header|REXX}}==

===version 1===

Call assert lcp("interspecies","interstellar","interstate"),"inters"

Call assert lcp("throne","throne"),"throne"

Leave

End

{{out}}

<pre>test lcp("interspecies","interstellar","interstate")

===version 2===

This REXX version makes use of the &nbsp; '''compare''' &nbsp; BIF.

say LCP('interspecies', "interstellar", 'interstate')

say LCP('throne', "throne") /*2 strings, they are exactly the same.*/

m= t - 1; @= left(@, max(0, m) ) /*define maximum. */

end /*j*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

===version 3===

This REXX version explicitly shows &nbsp; ''null'' &nbsp; values and the number of strings specified.

say LCP('interspecies', "interstellar", 'interstate')

say LCP('throne', "throne") /*2 strings, they are exactly the same.*/

return ' longest common prefix=' shownull(@) /*return answer. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

# Project : Longest common prefix

 

see comp + nl

ok

Output:

<pre>

inters

</pre>

 

=={{header|Ruby}}==

return "" if strs.empty?

min, max = strs.minmax

data.each do |set|

puts "lcp(#{set.inspect[1..-2]}) = #{lcp(*set).inspect}"

 

{{out}}

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.

 

fn main() {

let strs: [&[&[u8]]; 7] = [

}

}

 

'''Output:'''

> zip takeWhile: (i,i), (n,n), (t,t), (e,e), (r,r), (s,s) unzip < > "inters"

"intesteller" / \ i, n, t, e, r, s

test("shared start") {

assert(lcp("interspecies","interstellar","interstate") === "inters")

def lcp(list: String*) = list.foldLeft("")((_,_) =>

(list.min.view,list.max.view).zipped.takeWhile(v => v._1 == v._2).unzip._1.mkString)

 

=={{header|Sidef}}==

func find_common_prefix(hash, acc) {

if (hash.len == 1) {

 

return find_common_prefix(hash, '')

 

Demonstration:

["interspecies","interstellar","interstate"],

["throne","throne"],

data.each { |set|

say "lcp(#{set.dump.substr(1,-1)}) = #{lcp(set...).dump}";

{{out}}

<pre>

{{works with|Smalltalk/X}}

There is already a longestCommonPrefix method in Collection; however, if there wasn't, the following will do:

|end|

end := (a size) min:(b size).

) do:[:eachList |

Transcript show:eachList storeString; show:' ==> '; showCR:(lcp value:eachList)

{{out}}

<pre>#('interspecies' 'interstellar' 'interstate') ==> inters

 

=={{header|Standard ML}}==

let

val longerFirst = fn pair as (a, b) =>

in

fn [] => "" | x :: xs => foldl (commonPrefix o longerFirst) x xs

;Test<nowiki>:</nowiki>

["interspecies", "interstellar", "interstate"],

["throne", "throne"],

]

 

{{out}}

<pre>'inters'

 

=={{header|Swift}}==

return String(zip(string1, string2).prefix(while: {$0 == $1}).map{$0.0})

}

printLongestCommonPrefix([])

printLongestCommonPrefix(["prefix", "suffix"])

 

{{out}}

Since [http://www.tcl.tk/cgi-bin/tct/tip/195.html TIP#195] this has been present as a core command:

 

% prefix longest {interstellar interspecies interstate integer} ""

inte

 

=={{header|VBScript}}==

'declare an array

str = Split(s,",")

WScript.StdOut.Write "Test case " & n & " " & test(n) & " = " & lcp(test(n))

WScript.StdOut.WriteLine

 

{{out}}

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Function LongestCommonPrefix(ParamArray sa() As String) As String

End Sub

 

{{out}}

<pre>inters

 

foo</pre>

 

=={{header|Wren}}==

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

 

var lcp = Fn.new { |sa|

for (sa in lists) {

Fmt.print(" $-46s = $q", Fmt.v("q", 0, sa), lcp.call(sa))

 

{{out}}

 

=={{header|XProfan}}==

Parameters long liste

Declare int longest, j, L, string s,t

ClearList 0

WaitKey

{{out}}

<pre>

=={{header|zkl}}==

The string method prefix returns the number of common prefix characters.

Or, without using prefix:

{{trans|Scala}}

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

})

tester.testRun(lcp.fp("interspecies","interstellar","interstate"),Void,"inters",__LINE__);

tester.testRun(lcp.fp("throne","throne"),Void,"throne",__LINE__);

tester.testRun(lcp.fp(""),Void,"",__LINE__);

tester.testRun(lcp.fp("prefix","suffix"),Void,"",__LINE__);

The fp (partial application) method is used to delay running lcp until the tester actually tests.

{{out}}