Longest common prefix: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 27: | Line 27: | ||
=={{header|11l}}== |
=={{header|11l}}== |
||
< |
<syntaxhighlight lang="11l">F lcp(sa) |
||
I sa.empty |
I sa.empty |
||
R ‘’ |
R ‘’ |
||
Line 53: | Line 53: | ||
test([‘’]) |
test([‘’]) |
||
test([‘prefix’, ‘suffix’]) |
test([‘prefix’, ‘suffix’]) |
||
test([‘foo’, ‘foobar’])</ |
test([‘foo’, ‘foobar’])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 68: | Line 68: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">DEFINE PTR="CARD" |
||
BYTE Func Equals(CHAR ARRAY a,b) |
BYTE Func Equals(CHAR ARRAY a,b) |
||
Line 179: | Line 179: | ||
texts(0)=t10 texts(1)=t11 |
texts(0)=t10 texts(1)=t11 |
||
Test(texts,2) |
Test(texts,2) |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_common_prefix.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_common_prefix.png Screenshot from Atari 8-bit computer] |
||
Line 194: | Line 194: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
with Ada.Strings.Unbounded; |
with Ada.Strings.Unbounded; |
||
Line 264: | Line 264: | ||
Ada.Text_IO.Put_Line (Prefix); |
Ada.Text_IO.Put_Line (Prefix); |
||
end Longest_Prefix;</ |
end Longest_Prefix;</syntaxhighlight> |
||
=={{header|Aime}}== |
=={{header|Aime}}== |
||
< |
<syntaxhighlight lang="aime">lcp(...) |
||
{ |
{ |
||
integer n; |
integer n; |
||
Line 296: | Line 296: | ||
0; |
0; |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>"inters" |
<pre>"inters" |
||
Line 310: | Line 310: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}} |
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}} |
||
< |
<syntaxhighlight lang="algol68"># find the longest common prefix of two strings # |
||
PRIO COMMONPREFIX = 1; |
PRIO COMMONPREFIX = 1; |
||
OP COMMONPREFIX = ( STRING a, b )STRING: |
OP COMMONPREFIX = ( STRING a, b )STRING: |
||
Line 380: | Line 380: | ||
test prefix( ( "prefix", "suffix" ), "" ); |
test prefix( ( "prefix", "suffix" ), "" ); |
||
test prefix( ( "foo", "foobar" ), "foo" ) |
test prefix( ( "foo", "foobar" ), "foo" ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 396: | Line 396: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
===AppleScriptObjC=== |
===AppleScriptObjC=== |
||
< |
<syntaxhighlight lang="applescript">use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later |
||
use framework "Foundation" |
use framework "Foundation" |
||
Line 427: | Line 427: | ||
longestCommonPrefix({}) --> "" |
longestCommonPrefix({}) --> "" |
||
longestCommonPrefix({"prefix", "suffix"}) --> "" |
longestCommonPrefix({"prefix", "suffix"}) --> "" |
||
longestCommonPrefix({"foo", "foobar"}) --> "foo"</ |
longestCommonPrefix({"foo", "foobar"}) --> "foo"</syntaxhighlight> |
||
---- |
---- |
||
===Functional=== |
===Functional=== |
||
and for more productivity, and higher re-use of existing library functions, we can write a functional definition (rather than a procedure). |
and for more productivity, and higher re-use of existing library functions, we can write a functional definition (rather than a procedure). |
||
< |
<syntaxhighlight lang="applescript">------------------- LONGEST COMMON PREFIX ------------------ |
||
Line 776: | Line 776: | ||
set my text item delimiters to dlm |
set my text item delimiters to dlm |
||
str |
str |
||
end unlines</ |
end unlines</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>['interspecies', 'interstellar', 'interstate'] -> 'inters' |
<pre>['interspecies', 'interstellar', 'interstate'] -> 'inters' |
||
Line 789: | Line 789: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">lcp: function [lst][ |
||
ret: "" |
ret: "" |
||
idx: 0 |
idx: 0 |
||
Line 812: | Line 812: | ||
print lcp [""] |
print lcp [""] |
||
print lcp ["prefix" "suffix"] |
print lcp ["prefix" "suffix"] |
||
print lcp ["foo" "foobar"]</ |
print lcp ["foo" "foobar"]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 826: | Line 826: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">lcp(data){ |
||
for num, v in StrSplit(data.1) |
for num, v in StrSplit(data.1) |
||
for i, word in data |
for i, word in data |
||
Line 832: | Line 832: | ||
return SubStr(word, 1, num-1) |
return SubStr(word, 1, num-1) |
||
return SubStr(word, 1, num) |
return SubStr(word, 1, num) |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">MsgBox % "" |
||
. "`n" lcp(["interspecies","interstellar","interstate"]) |
. "`n" lcp(["interspecies","interstellar","interstate"]) |
||
. "`n" lcp(["throne","throne"]) |
. "`n" lcp(["throne","throne"]) |
||
Line 843: | Line 843: | ||
. "`n" lcp(["prefix","suffix"]) |
. "`n" lcp(["prefix","suffix"]) |
||
. "`n" lcp(["foo","foobar"]) |
. "`n" lcp(["foo","foobar"]) |
||
return</ |
return</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 857: | Line 857: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f LONGEST_COMMON_PREFIX.AWK |
# syntax: GAWK -f LONGEST_COMMON_PREFIX.AWK |
||
BEGIN { |
BEGIN { |
||
Line 904: | Line 904: | ||
return(substr(str,1,lcp_leng)) |
return(substr(str,1,lcp_leng)) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<p>Output:</p> |
<p>Output:</p> |
||
<pre> |
<pre> |
||
Line 918: | Line 918: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<syntaxhighlight lang="c"> |
|||
<lang C> |
|||
#include<stdarg.h> |
#include<stdarg.h> |
||
#include<string.h> |
#include<string.h> |
||
Line 980: | Line 980: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 996: | Line 996: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
namespace LCP { |
namespace LCP { |
||
Line 1,039: | Line 1,039: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>inters |
<pre>inters |
||
Line 1,052: | Line 1,052: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <set> |
||
#include <algorithm> |
#include <algorithm> |
||
#include <string> |
#include <string> |
||
Line 1,129: | Line 1,129: | ||
std::cout << "lcp( \"foo\" , \"foobar\" ) = " << lcp ( input ) << std::endl ; |
std::cout << "lcp( \"foo\" , \"foobar\" ) = " << lcp ( input ) << std::endl ; |
||
return 0 ; |
return 0 ; |
||
}</ |
}</syntaxhighlight> |
||
Another more concise version (C++14 for comparing dissimilar containers): |
Another more concise version (C++14 for comparing dissimilar containers): |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <algorithm> |
#include <algorithm> |
||
#include <string> |
#include <string> |
||
Line 1,171: | Line 1,171: | ||
return 0 ; |
return 0 ; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,183: | Line 1,183: | ||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
< |
<syntaxhighlight lang="clu">lcp = proc (strs: ss) returns (string) |
||
ss = sequence[string] |
ss = sequence[string] |
||
if ss$empty(strs) then return("") end |
if ss$empty(strs) then return("") end |
||
Line 1,225: | Line 1,225: | ||
stream$putl(po, "\"" || lcp(test) || "\"") |
stream$putl(po, "\"" || lcp(test) || "\"") |
||
end |
end |
||
end start_up</ |
end start_up</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>"inters" |
<pre>"inters" |
||
Line 1,239: | Line 1,239: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="d">import std.stdio; |
||
string lcp(string[] list ...) { |
string lcp(string[] list ...) { |
||
Line 1,272: | Line 1,272: | ||
writeln(lcp("prefix","suffix")); |
writeln(lcp("prefix","suffix")); |
||
writeln(lcp("foo","foobar")); |
writeln(lcp("foo","foobar")); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>inters |
<pre>inters |
||
Line 1,287: | Line 1,287: | ||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="dyalect">func lcp(sa...) { |
||
if sa.Length() == 0 || !sa[0] { |
if sa.Length() == 0 || !sa[0] { |
||
return "" |
return "" |
||
Line 1,322: | Line 1,322: | ||
print(lcp(nil)) |
print(lcp(nil)) |
||
print(lcp("prefix", "suffix")) |
print(lcp("prefix", "suffix")) |
||
print(lcp("foo", "foobar"))</ |
print(lcp("foo", "foobar"))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,337: | Line 1,337: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="lisp"> |
||
;; find common prefix of two strings |
;; find common prefix of two strings |
||
(define (prefix s t ) (for/string ((u s) (v t)) #:break (not (= u v)) u)) |
(define (prefix s t ) (for/string ((u s) (v t)) #:break (not (= u v)) u)) |
||
Line 1,368: | Line 1,368: | ||
("prefix" "suffix") → "" |
("prefix" "suffix") → "" |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir"> |
||
defmodule LCP do |
defmodule LCP do |
||
@data [ |
@data [ |
||
Line 1,399: | Line 1,399: | ||
defp lcp( _, _, pre), do: String.reverse(pre) |
defp lcp( _, _, pre), do: String.reverse(pre) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,415: | Line 1,415: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang="erlang"> |
||
-module(lcp). |
-module(lcp). |
||
-export([ main/0 ]). |
-export([ main/0 ]). |
||
Line 1,438: | Line 1,438: | ||
lcp([X|Xs], [X|Ys], Pre) -> lcp(Xs, Ys, [X|Pre]); |
lcp([X|Xs], [X|Ys], Pre) -> lcp(Xs, Ys, [X|Pre]); |
||
lcp( _, _, Pre) -> lists:reverse(Pre). |
lcp( _, _, Pre) -> lists:reverse(Pre). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,454: | Line 1,454: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: continuations formatting fry kernel sequences strings ; |
||
IN: rosetta-code.lcp |
IN: rosetta-code.lcp |
||
Line 1,480: | Line 1,480: | ||
} [ dup lcp "%u lcp = %u\n" printf ] each ; |
} [ dup lcp "%u lcp = %u\n" printf ] each ; |
||
MAIN: lcp-demo</ |
MAIN: lcp-demo</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,495: | Line 1,495: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
Function lcp(s() As String) As String |
Function lcp(s() As String) As String |
||
Line 1,556: | Line 1,556: | ||
Print |
Print |
||
Print "Press any key to quit" |
Print "Press any key to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,572: | Line 1,572: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,625: | Line 1,625: | ||
fmt.Printf("lcp(%q) = %q\n", l, lcp(l)) |
fmt.Printf("lcp(%q) = %q\n", l, lcp(l)) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,641: | Line 1,641: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
This even works on infinite strings (that have a finite longest common prefix), due to Haskell's laziness. |
This even works on infinite strings (that have a finite longest common prefix), due to Haskell's laziness. |
||
< |
<syntaxhighlight lang="haskell">import Data.List (intercalate, transpose) |
||
lcp :: (Eq a) => [[a]] -> [a] |
lcp :: (Eq a) => [[a]] -> [a] |
||
Line 1,664: | Line 1,664: | ||
showPrefix :: [String] -> String |
showPrefix :: [String] -> String |
||
showPrefix = ((<>) . (<> " -> ") . show) <*> (show . lcp)</ |
showPrefix = ((<>) . (<> " -> ") . show) <*> (show . lcp)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>["interspecies","interstellar","interstate"] -> "inters" |
<pre>["interspecies","interstellar","interstate"] -> "inters" |
||
Line 1,678: | Line 1,678: | ||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j">lcp=: {. {.~ 0 i.~ [: */2 =/\ ]</syntaxhighlight> |
||
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. |
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. |
||
Line 1,688: | Line 1,688: | ||
Examples: |
Examples: |
||
< |
<syntaxhighlight lang="j"> lcp 'interspecies','interstellar',:'interstate' |
||
inters |
inters |
||
lcp 'throne',:'throne' |
lcp 'throne',:'throne' |
||
Line 1,701: | Line 1,701: | ||
lcp 'prefix',:'suffix' |
lcp 'prefix',:'suffix' |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
< |
<syntaxhighlight lang="java5">public class LCP { |
||
public static String lcp(String... list){ |
public static String lcp(String... list){ |
||
if(list == null) return "";//special case |
if(list == null) return "";//special case |
||
Line 1,740: | Line 1,740: | ||
System.out.println(lcp("foo","foobar")); |
System.out.println(lcp("foo","foobar")); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>inters |
<pre>inters |
||
Line 1,756: | Line 1,756: | ||
===ES5=== |
===ES5=== |
||
< |
<syntaxhighlight lang="javascript">(function () { |
||
'use strict'; |
'use strict'; |
||
Line 1,817: | Line 1,817: | ||
]; |
]; |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="javascript">[true, true, true, true, true, true, true]</syntaxhighlight> |
||
Line 1,832: | Line 1,832: | ||
This functionally implemented zip is significantly slower than the iterative version used above: |
This functionally implemented zip is significantly slower than the iterative version used above: |
||
< |
<syntaxhighlight lang="javascript">// Zip arbitrary number of lists (a functional implementation, this time) |
||
// Accepts arrays or strings, and returns [[a]] |
// Accepts arrays or strings, and returns [[a]] |
||
function zip() { |
function zip() { |
||
Line 1,852: | Line 1,852: | ||
}, null) |
}, null) |
||
} else return []; |
} else return []; |
||
}</ |
}</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
"use strict"; |
"use strict"; |
||
Line 1,948: | Line 1,948: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>["interspecies","interstellar","interstate"] -> "inters" |
<pre>["interspecies","interstellar","interstate"] -> "inters" |
||
Line 1,963: | Line 1,963: | ||
See [[#Scala]] for a description of the approach used in this section. |
See [[#Scala]] for a description of the approach used in this section. |
||
< |
<syntaxhighlight lang="jq"># If your jq includes until/2 |
||
# then feel free to omit the following definition: |
# then feel free to omit the following definition: |
||
def until(cond; next): |
def until(cond; next): |
||
def _until: if cond then . else (next|_until) end; _until;</ |
def _until: if cond then . else (next|_until) end; _until;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq">def longest_common_prefix: |
||
if length == 0 then "" # by convention |
if length == 0 then "" # by convention |
||
elif length == 1 then .[0] # for speed |
elif length == 1 then .[0] # for speed |
||
Line 1,979: | Line 1,979: | ||
| $first[0:.] |
| $first[0:.] |
||
end |
end |
||
end;</ |
end;</syntaxhighlight> |
||
'''Test Cases''' |
'''Test Cases''' |
||
< |
<syntaxhighlight lang="jq">def check(ans): longest_common_prefix == ans; |
||
(["interspecies","interstellar","interstate"] | check("inters")) and |
(["interspecies","interstellar","interstate"] | check("inters")) and |
||
Line 1,993: | Line 1,993: | ||
(["prefix","suffix"] | check("")) and |
(["prefix","suffix"] | check("")) and |
||
(["foo","foobar"] | check("foo")) |
(["foo","foobar"] | check("foo")) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="sh">$ jq -n -f longest_common_prefix.jq |
||
true</ |
true</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
< |
<syntaxhighlight lang="julia">function lcp(str::AbstractString...) |
||
r = IOBuffer() |
r = IOBuffer() |
||
str = [str...] |
str = [str...] |
||
Line 2,022: | Line 2,022: | ||
@show lcp() |
@show lcp() |
||
@show lcp("prefix","suffix") |
@show lcp("prefix","suffix") |
||
@show lcp("foo","foobar")</ |
@show lcp("foo","foobar")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,036: | Line 2,036: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.0.6 |
||
fun lcp(vararg sa: String): String { |
fun lcp(vararg sa: String): String { |
||
Line 2,064: | Line 2,064: | ||
println("""["prefix","suffix"] = "${lcp("prefix", "suffix")}"""") |
println("""["prefix","suffix"] = "${lcp("prefix", "suffix")}"""") |
||
println("""["foo","foobar"] = "${lcp("foo", "foobar")}"""") |
println("""["foo","foobar"] = "${lcp("foo", "foobar")}"""") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,083: | Line 2,083: | ||
=={{header|Lobster}}== |
=={{header|Lobster}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="lobster">// lcp finds the longest common prefix of the input strings |
||
def lcp(l): |
def lcp(l): |
||
Line 2,119: | Line 2,119: | ||
["prefix", "suffix"], |
["prefix", "suffix"], |
||
["foo", "foobar"]]): |
["foo", "foobar"]]): |
||
print("lcp" + _ + " = \"" + lcp(_) + "\"")</ |
print("lcp" + _ + " = \"" + lcp(_) + "\"")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>lcp["interspecies", "interstellar", "interstate"] = "inters" |
<pre>lcp["interspecies", "interstellar", "interstate"] = "inters" |
||
Line 2,133: | Line 2,133: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">function lcp (strList) |
||
local shortest, prefix, first = math.huge, "" |
local shortest, prefix, first = math.huge, "" |
||
for _, str in pairs(strList) do |
for _, str in pairs(strList) do |
||
Line 2,168: | Line 2,168: | ||
pre = lcp(stringList) |
pre = lcp(stringList) |
||
if pre == "" then print(string.char(238)) else print(pre) end |
if pre == "" then print(string.char(238)) else print(pre) end |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>inters |
<pre>inters |
||
Line 2,181: | Line 2,181: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang="maple">lcp := proc(arr) |
||
local A: |
local A: |
||
if (arr = []) then return "": end if: |
if (arr = []) then return "": end if: |
||
A := sort(arr): |
A := sort(arr): |
||
return (A[1][1..(StringTools:-CommonPrefix(A[1],A[-1]))]): |
return (A[1][1..(StringTools:-CommonPrefix(A[1],A[-1]))]): |
||
end proc:</ |
end proc:</syntaxhighlight> |
||
'''Test Cases''' |
'''Test Cases''' |
||
< |
<syntaxhighlight lang="maple">lcp(["interspecies","interstellar","interstate"]); |
||
lcp(["throne","throne"]); |
lcp(["throne","throne"]); |
||
lcp(["throne","dungeon"]); |
lcp(["throne","dungeon"]); |
||
Line 2,196: | Line 2,196: | ||
lcp([]); |
lcp([]); |
||
lcp(["prefix","suffix"]); |
lcp(["prefix","suffix"]); |
||
lcp(["foo","foobar"]);</ |
lcp(["foo","foobar"]);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>inters |
<pre>inters |
||
Line 2,209: | Line 2,209: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[LCP] |
||
LCP[x_List] := Module[{l, s}, |
LCP[x_List] := Module[{l, s}, |
||
If[Length[x] > 0, |
If[Length[x] > 0, |
||
Line 2,229: | Line 2,229: | ||
LCP[{}] |
LCP[{}] |
||
LCP[{"prefix", "suffix"}] |
LCP[{"prefix", "suffix"}] |
||
LCP[{"foo", "foobar"}]</ |
LCP[{"foo", "foobar"}]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>"inters" |
<pre>"inters" |
||
Line 2,242: | Line 2,242: | ||
=={{header|MATLAB}} / {{header|Octave}}== |
=={{header|MATLAB}} / {{header|Octave}}== |
||
<syntaxhighlight lang="matlab"> |
|||
<lang Matlab> |
|||
function lcp = longest_common_prefix(varargin) |
function lcp = longest_common_prefix(varargin) |
||
ca = char(varargin); |
ca = char(varargin); |
||
Line 2,250: | Line 2,250: | ||
longest_common_prefix('aa', 'aa', 'aac') |
longest_common_prefix('aa', 'aa', 'aac') |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,259: | Line 2,259: | ||
=={{header|MiniScript}}== |
=={{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. |
We find the shortest and longest strings (without sorting, which makes the code slightly longer but much more efficient), and then just compare those. |
||
< |
<syntaxhighlight lang="miniscript">lcp = function(strList) |
||
if not strList then return null |
if not strList then return null |
||
// find the shortest and longest strings (without sorting!) |
// find the shortest and longest strings (without sorting!) |
||
Line 2,282: | Line 2,282: | ||
print lcp(["cheese"]) |
print lcp(["cheese"]) |
||
print lcp([]) |
print lcp([]) |
||
print lcp(["foo","foobar"])</ |
print lcp(["foo","foobar"])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,295: | Line 2,295: | ||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="modula2">MODULE LCP; |
||
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
||
Line 2,366: | Line 2,366: | ||
ReadChar |
ReadChar |
||
END LCP.</ |
END LCP.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>inters |
<pre>inters |
||
Line 2,377: | Line 2,377: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import sequtils, strformat, strutils |
||
func lcp(list: varargs[string]): string = |
func lcp(list: varargs[string]): string = |
||
Line 2,402: | Line 2,402: | ||
test() |
test() |
||
test("prefix", "suffix") |
test("prefix", "suffix") |
||
test("foo", "foobar")</ |
test("foo", "foobar")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,415: | Line 2,415: | ||
=={{header|Ol}}== |
=={{header|Ol}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
(define (lcp . args) |
(define (lcp . args) |
||
(if (null? args) |
(if (null? args) |
||
Line 2,434: | Line 2,434: | ||
(print "> " (lcp "prefix" "suffix")) |
(print "> " (lcp "prefix" "suffix")) |
||
(print "> " (lcp "foo" "foobar")) |
(print "> " (lcp "foo" "foobar")) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{Out} |
{Out} |
||
<pre> |
<pre> |
||
Line 2,450: | Line 2,450: | ||
==ooRexx== |
==ooRexx== |
||
{{trans|REXX}} |
{{trans|REXX}} |
||
< |
<syntaxhighlight 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","throne")),"throne" |
||
Call assert lcp(.list~of("throne","dungeon")),"" |
Call assert lcp(.list~of("throne","dungeon")),"" |
||
Line 2,485: | Line 2,485: | ||
Leave |
Leave |
||
End |
End |
||
Return left(arg(1),i-1)</ |
Return left(arg(1),i-1)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>lcp(interspecies,interstellar,interstate) |
<pre>lcp(interspecies,interstellar,interstate) |
||
Line 2,512: | Line 2,512: | ||
If the strings are known not to contain null-bytes, we can let the regex backtracking engine find the longest common prefix like this: |
If the strings are known not to contain null-bytes, we can let the regex backtracking engine find the longest common prefix like this: |
||
< |
<syntaxhighlight lang="perl">sub lcp { |
||
(join("\0", @_) =~ /^ ([^\0]*) [^\0]* (?:\0 \1 [^\0]*)* $/sx)[0]; |
(join("\0", @_) =~ /^ ([^\0]*) [^\0]* (?:\0 \1 [^\0]*)* $/sx)[0]; |
||
}</ |
}</syntaxhighlight> |
||
Testing: |
Testing: |
||
< |
<syntaxhighlight lang="perl">use Test::More; |
||
plan tests => 8; |
plan tests => 8; |
||
Line 2,527: | Line 2,527: | ||
is lcp(), ""; |
is lcp(), ""; |
||
is lcp("prefix","suffix"), ""; |
is lcp("prefix","suffix"), ""; |
||
is lcp("foo","foobar"), "foo";</ |
is lcp("foo","foobar"), "foo";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,533: | Line 2,533: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">lcp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">strings</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">lcp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">strings</span><span style="color: #0000FF;">)</span> |
||
Line 2,566: | Line 2,566: | ||
<span style="color: #0000FF;">?</span><span style="color: #000000;">lcp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
<span style="color: #0000FF;">?</span><span style="color: #000000;">lcp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,582: | Line 2,582: | ||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
{{trans|REXX}} |
{{trans|REXX}} |
||
< |
<syntaxhighlight lang="pli">*process source xref attributes or(!); |
||
(subrg): |
(subrg): |
||
lcpt: Proc Options(main); |
lcpt: Proc Options(main); |
||
Line 2,634: | Line 2,634: | ||
End; |
End; |
||
End;</ |
End;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>"interspecies interstellar interstate" |
<pre>"interspecies interstellar interstate" |
||
Line 2,658: | Line 2,658: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function lcp ($arr) { |
function lcp ($arr) { |
||
if($arr){ |
if($arr){ |
||
Line 2,686: | Line 2,686: | ||
show @("prefix","suffix") |
show @("prefix","suffix") |
||
show @("foo","foobar") |
show @("foo","foobar") |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 2,702: | Line 2,702: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
{{works with|SWI Prolog}} |
{{works with|SWI Prolog}} |
||
< |
<syntaxhighlight lang="prolog">common_prefix(String1, String2, Prefix):- |
||
string_chars(String1, Chars1), |
string_chars(String1, Chars1), |
||
string_chars(String2, Chars2), |
string_chars(String2, Chars2), |
||
Line 2,736: | Line 2,736: | ||
test([]), |
test([]), |
||
test(["prefix", "suffix"]), |
test(["prefix", "suffix"]), |
||
test(["foo", "foobar"]).</ |
test(["foo", "foobar"]).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,754: | Line 2,754: | ||
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]]. |
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]]. |
||
< |
<syntaxhighlight lang="python">import os.path |
||
def lcp(*s): |
def lcp(*s): |
||
Line 2,765: | Line 2,765: | ||
assert lcp("") == "" |
assert lcp("") == "" |
||
assert lcp("prefix","suffix") == "" |
assert lcp("prefix","suffix") == "" |
||
assert lcp("foo","foobar") == "foo"</ |
assert lcp("foo","foobar") == "foo"</syntaxhighlight> |
||
===Python: Functional=== |
===Python: Functional=== |
||
To see if all the n'th characters are the same I compare the min and max characters in the lambda function. |
To see if all the n'th characters are the same I compare the min and max characters in the lambda function. |
||
< |
<syntaxhighlight lang="python">from itertools import takewhile |
||
def lcp(*s): |
def lcp(*s): |
||
Line 2,782: | Line 2,782: | ||
assert lcp("") == "" |
assert lcp("") == "" |
||
assert lcp("prefix","suffix") == "" |
assert lcp("prefix","suffix") == "" |
||
assert lcp("foo","foobar") == "foo"</ |
assert lcp("foo","foobar") == "foo"</syntaxhighlight> |
||
The above runs without output. |
The above runs without output. |
||
Line 2,788: | Line 2,788: | ||
;Alternative Functional: |
;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. |
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. |
||
< |
<syntaxhighlight lang="python">from itertools import takewhile |
||
def lcp(*s): |
def lcp(*s): |
||
return ''.join(a for a,b in takewhile(lambda x: x[0] == x[1], |
return ''.join(a for a,b in takewhile(lambda x: x[0] == x[1], |
||
zip(min(s), max(s))))</ |
zip(min(s), max(s))))</syntaxhighlight> |
||
Or, defined in terms of a generic '''transpose''' function: |
Or, defined in terms of a generic '''transpose''' function: |
||
< |
<syntaxhighlight lang="python">from itertools import (takewhile) |
||
Line 2,845: | Line 2,845: | ||
# TEST --- |
# TEST --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[interspecies, interstellar, interstate] -> inters |
<pre>[interspecies, interstellar, interstate] -> inters |
||
Line 2,857: | Line 2,857: | ||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
<lang> [ dup [] = iff |
<syntaxhighlight lang="text"> [ dup [] = iff |
||
[ drop true ] done |
[ drop true ] done |
||
true swap |
true swap |
||
Line 2,918: | Line 2,918: | ||
$ "foo foobar" |
$ "foo foobar" |
||
nest$ commonprefix echoresult</ |
nest$ commonprefix echoresult</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,937: | Line 2,937: | ||
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. |
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. |
||
<lang>#lang racket |
<syntaxhighlight lang="text">#lang racket |
||
(require srfi/1) |
(require srfi/1) |
||
Line 2,960: | Line 2,960: | ||
(lcp ε) => ε |
(lcp ε) => ε |
||
(lcp) => ε |
(lcp) => ε |
||
(lcp "prefix" "suffix") => ε))</ |
(lcp "prefix" "suffix") => ε))</syntaxhighlight> |
||
All tests pass. |
All tests pass. |
||
Line 2,968: | Line 2,968: | ||
{{works with|rakudo|2015-11-28}} |
{{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. |
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. |
||
<lang |
<syntaxhighlight lang="raku" line>multi lcp() { '' } |
||
multi lcp($s) { ~$s } |
multi lcp($s) { ~$s } |
||
multi lcp(*@s) { substr @s[0], 0, [+] [\and] [Zeqv] |@s».ords } |
multi lcp(*@s) { substr @s[0], 0, [+] [\and] [Zeqv] |@s».ords } |
||
Line 2,982: | Line 2,982: | ||
is lcp(), ''; |
is lcp(), ''; |
||
is lcp("prefix","suffix"), ''; |
is lcp("prefix","suffix"), ''; |
||
is lcp("foo","foobar"), 'foo';</ |
is lcp("foo","foobar"), 'foo';</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1..8 |
<pre>1..8 |
||
Line 2,996: | Line 2,996: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
===version 1=== |
||
< |
<syntaxhighlight lang="rexx">/* REXX */ |
||
Call assert lcp("interspecies","interstellar","interstate"),"inters" |
Call assert lcp("interspecies","interstellar","interstate"),"inters" |
||
Call assert lcp("throne","throne"),"throne" |
Call assert lcp("throne","throne"),"throne" |
||
Line 3,036: | Line 3,036: | ||
Leave |
Leave |
||
End |
End |
||
Return left(arg(1),i-1)</ |
Return left(arg(1),i-1)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>test lcp("interspecies","interstellar","interstate") |
<pre>test lcp("interspecies","interstellar","interstate") |
||
Line 3,067: | Line 3,067: | ||
===version 2=== |
===version 2=== |
||
This REXX version makes use of the '''compare''' BIF. |
This REXX version makes use of the '''compare''' BIF. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program computes the longest common prefix (LCP) of any number of strings.*/ |
||
say LCP('interspecies', "interstellar", 'interstate') |
say LCP('interspecies', "interstellar", 'interstate') |
||
say LCP('throne', "throne") /*2 strings, they are exactly the same.*/ |
say LCP('throne', "throne") /*2 strings, they are exactly the same.*/ |
||
Line 3,089: | Line 3,089: | ||
m= t - 1; @= left(@, max(0, m) ) /*define maximum. */ |
m= t - 1; @= left(@, max(0, m) ) /*define maximum. */ |
||
end /*j*/ |
end /*j*/ |
||
return ' longest common prefix=' @ /*return answer. */</ |
return ' longest common prefix=' @ /*return answer. */</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 3,136: | Line 3,136: | ||
===version 3=== |
===version 3=== |
||
This REXX version explicitly shows ''null'' values and the number of strings specified. |
This REXX version explicitly shows ''null'' values and the number of strings specified. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program computes the longest common prefix (LCP) of any number of strings.*/ |
||
say LCP('interspecies', "interstellar", 'interstate') |
say LCP('interspecies', "interstellar", 'interstate') |
||
say LCP('throne', "throne") /*2 strings, they are exactly the same.*/ |
say LCP('throne', "throne") /*2 strings, they are exactly the same.*/ |
||
Line 3,162: | Line 3,162: | ||
return ' longest common prefix=' shownull(@) /*return answer. */ |
return ' longest common prefix=' shownull(@) /*return answer. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
showNull: procedure; parse arg z; if z=='' then z= "«null»"; return z</ |
showNull: procedure; parse arg z; if z=='' then z= "«null»"; return z</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 3,218: | Line 3,218: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Longest common prefix |
# Project : Longest common prefix |
||
Line 3,249: | Line 3,249: | ||
see comp + nl |
see comp + nl |
||
ok |
ok |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 3,256: | Line 3,256: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">def lcp(*strs) |
||
return "" if strs.empty? |
return "" if strs.empty? |
||
min, max = strs.minmax |
min, max = strs.minmax |
||
Line 3,277: | Line 3,277: | ||
data.each do |set| |
data.each do |set| |
||
puts "lcp(#{set.inspect[1..-2]}) = #{lcp(*set).inspect}" |
puts "lcp(#{set.inspect[1..-2]}) = #{lcp(*set).inspect}" |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,296: | Line 3,296: | ||
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. |
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. |
||
<syntaxhighlight lang="rust"> |
|||
<lang Rust> |
|||
fn main() { |
fn main() { |
||
let strs: [&[&[u8]]; 7] = [ |
let strs: [&[&[u8]]; 7] = [ |
||
Line 3,339: | Line 3,339: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Output:''' |
'''Output:''' |
||
Line 3,358: | Line 3,358: | ||
> zip takeWhile: (i,i), (n,n), (t,t), (e,e), (r,r), (s,s) unzip < > "inters" |
> zip takeWhile: (i,i), (n,n), (t,t), (e,e), (r,r), (s,s) unzip < > "inters" |
||
"intesteller" / \ i, n, t, e, r, s |
"intesteller" / \ i, n, t, e, r, s |
||
</pre>< |
</pre><syntaxhighlight lang="scala">class TestLCP extends FunSuite { |
||
test("shared start") { |
test("shared start") { |
||
assert(lcp("interspecies","interstellar","interstate") === "inters") |
assert(lcp("interspecies","interstellar","interstate") === "inters") |
||
Line 3,371: | Line 3,371: | ||
def lcp(list: String*) = list.foldLeft("")((_,_) => |
def lcp(list: String*) = list.foldLeft("")((_,_) => |
||
(list.min.view,list.max.view).zipped.takeWhile(v => v._1 == v._2).unzip._1.mkString) |
(list.min.view,list.max.view).zipped.takeWhile(v => v._1 == v._2).unzip._1.mkString) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby"># Finds the first point where the tree bifurcates |
||
func find_common_prefix(hash, acc) { |
func find_common_prefix(hash, acc) { |
||
if (hash.len == 1) { |
if (hash.len == 1) { |
||
Line 3,402: | Line 3,402: | ||
return find_common_prefix(hash, '') |
return find_common_prefix(hash, '') |
||
}</ |
}</syntaxhighlight> |
||
Demonstration: |
Demonstration: |
||
< |
<syntaxhighlight lang="ruby">var data = [ |
||
["interspecies","interstellar","interstate"], |
["interspecies","interstellar","interstate"], |
||
["throne","throne"], |
["throne","throne"], |
||
Line 3,419: | Line 3,419: | ||
data.each { |set| |
data.each { |set| |
||
say "lcp(#{set.dump.substr(1,-1)}) = #{lcp(set...).dump}"; |
say "lcp(#{set.dump.substr(1,-1)}) = #{lcp(set...).dump}"; |
||
};</ |
};</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,436: | Line 3,436: | ||
{{works with|Smalltalk/X}} |
{{works with|Smalltalk/X}} |
||
There is already a longestCommonPrefix method in Collection; however, if there wasn't, the following will do: |
There is already a longestCommonPrefix method in Collection; however, if there wasn't, the following will do: |
||
< |
<syntaxhighlight lang="smalltalk">prefixLength := [:a :b | |
||
|end| |
|end| |
||
end := (a size) min:(b size). |
end := (a size) min:(b size). |
||
Line 3,464: | Line 3,464: | ||
) do:[:eachList | |
) do:[:eachList | |
||
Transcript show:eachList storeString; show:' ==> '; showCR:(lcp value:eachList) |
Transcript show:eachList storeString; show:' ==> '; showCR:(lcp value:eachList) |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>#('interspecies' 'interstellar' 'interstate') ==> inters |
<pre>#('interspecies' 'interstellar' 'interstate') ==> inters |
||
Line 3,477: | Line 3,477: | ||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
< |
<syntaxhighlight lang="sml">val lcp = |
||
let |
let |
||
val longerFirst = fn pair as (a, b) => |
val longerFirst = fn pair as (a, b) => |
||
Line 3,487: | Line 3,487: | ||
in |
in |
||
fn [] => "" | x :: xs => foldl (commonPrefix o longerFirst) x xs |
fn [] => "" | x :: xs => foldl (commonPrefix o longerFirst) x xs |
||
end</ |
end</syntaxhighlight> |
||
;Test<nowiki>:</nowiki> |
;Test<nowiki>:</nowiki> |
||
< |
<syntaxhighlight lang="sml">val test = [ |
||
["interspecies", "interstellar", "interstate"], |
["interspecies", "interstellar", "interstate"], |
||
["throne", "throne"], |
["throne", "throne"], |
||
Line 3,501: | Line 3,501: | ||
] |
] |
||
val () = (print o concat o map (fn lst => "'" ^ lcp lst ^ "'\n")) test</ |
val () = (print o concat o map (fn lst => "'" ^ lcp lst ^ "'\n")) test</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>'inters' |
<pre>'inters' |
||
Line 3,514: | Line 3,514: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">func commonPrefix(string1: String, string2: String) -> String { |
||
return String(zip(string1, string2).prefix(while: {$0 == $1}).map{$0.0}) |
return String(zip(string1, string2).prefix(while: {$0 == $1}).map{$0.0}) |
||
} |
} |
||
Line 3,541: | Line 3,541: | ||
printLongestCommonPrefix([]) |
printLongestCommonPrefix([]) |
||
printLongestCommonPrefix(["prefix", "suffix"]) |
printLongestCommonPrefix(["prefix", "suffix"]) |
||
printLongestCommonPrefix(["foo", "foobar"])</ |
printLongestCommonPrefix(["foo", "foobar"])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,560: | Line 3,560: | ||
Since [http://www.tcl.tk/cgi-bin/tct/tip/195.html TIP#195] this has been present as a core command: |
Since [http://www.tcl.tk/cgi-bin/tct/tip/195.html TIP#195] this has been present as a core command: |
||
< |
<syntaxhighlight lang="tcl">% namespace import ::tcl::prefix |
||
% prefix longest {interstellar interspecies interstate integer} "" |
% prefix longest {interstellar interspecies interstate integer} "" |
||
inte |
inte |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |
||
{{works with|bash}} |
{{works with|bash}} |
||
< |
<syntaxhighlight lang="bash">#!/bin/bash |
||
lcp () { |
lcp () { |
||
Line 3,613: | Line 3,613: | ||
printf '%s -> "%s"\n' "$(declare -p words)" "$(lcp "${words[@]}")" |
printf '%s -> "%s"\n' "$(declare -p words)" "$(lcp "${words[@]}")" |
||
done |
done |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,627: | Line 3,627: | ||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
< |
<syntaxhighlight lang="vb">Function lcp(s) |
||
'declare an array |
'declare an array |
||
str = Split(s,",") |
str = Split(s,",") |
||
Line 3,679: | Line 3,679: | ||
WScript.StdOut.Write "Test case " & n & " " & test(n) & " = " & lcp(test(n)) |
WScript.StdOut.Write "Test case " & n & " " & test(n) & " = " & lcp(test(n)) |
||
WScript.StdOut.WriteLine |
WScript.StdOut.WriteLine |
||
Next</ |
Next</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,691: | Line 3,691: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Module Module1 |
||
Function LongestCommonPrefix(ParamArray sa() As String) As String |
Function LongestCommonPrefix(ParamArray sa() As String) As String |
||
Line 3,736: | Line 3,736: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>inters |
<pre>inters |
||
Line 3,750: | Line 3,750: | ||
=={{header|Vlang}}== |
=={{header|Vlang}}== |
||
{{trans|go}} |
{{trans|go}} |
||
< |
<syntaxhighlight lang="vlang">// lcp finds the longest common prefix of the input strings. |
||
fn lcp(l []string) string { |
fn lcp(l []string) string { |
||
// Special cases first |
// Special cases first |
||
Line 3,798: | Line 3,798: | ||
println("lcp($l) = ${lcp(l)}") |
println("lcp($l) = ${lcp(l)}") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Same as Go entry</pre> |
<pre>Same as Go entry</pre> |
||
Line 3,805: | Line 3,805: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt |
||
var lcp = Fn.new { |sa| |
var lcp = Fn.new { |sa| |
||
Line 3,836: | Line 3,836: | ||
for (sa in lists) { |
for (sa in lists) { |
||
Fmt.print(" $-46s = $q", Fmt.v("q", 0, sa), lcp.call(sa)) |
Fmt.print(" $-46s = $q", Fmt.v("q", 0, sa), lcp.call(sa)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,854: | Line 3,854: | ||
=={{header|XProfan}}== |
=={{header|XProfan}}== |
||
< |
<syntaxhighlight lang="xprofan">Proc lcp |
||
Parameters long liste |
Parameters long liste |
||
Declare int longest, j, L, string s,t |
Declare int longest, j, L, string s,t |
||
Line 3,900: | Line 3,900: | ||
ClearList 0 |
ClearList 0 |
||
WaitKey |
WaitKey |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,915: | Line 3,915: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
The string method prefix returns the number of common prefix characters. |
The string method prefix returns the number of common prefix characters. |
||
< |
<syntaxhighlight lang="zkl">fcn lcp(s,strings){ s[0,s.prefix(vm.pasteArgs(1))] }</syntaxhighlight> |
||
Or, without using prefix: |
Or, without using prefix: |
||
{{trans|Scala}} |
{{trans|Scala}} |
||
< |
<syntaxhighlight lang="zkl">fcn lcp(strings){ |
||
vm.arglist.reduce(fcn(prefix,s){ Utils.Helpers.zipW(prefix,s) // lazy zip |
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 }) |
.pump(String,fcn([(a,b)]){ a==b and a or Void.Stop }) |
||
}) |
}) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">tester:=TheVault.Test.UnitTester.UnitTester(); |
||
tester.testRun(lcp.fp("interspecies","interstellar","interstate"),Void,"inters",__LINE__); |
tester.testRun(lcp.fp("interspecies","interstellar","interstate"),Void,"inters",__LINE__); |
||
tester.testRun(lcp.fp("throne","throne"),Void,"throne",__LINE__); |
tester.testRun(lcp.fp("throne","throne"),Void,"throne",__LINE__); |
||
Line 3,930: | Line 3,930: | ||
tester.testRun(lcp.fp(""),Void,"",__LINE__); |
tester.testRun(lcp.fp(""),Void,"",__LINE__); |
||
tester.testRun(lcp.fp("prefix","suffix"),Void,"",__LINE__); |
tester.testRun(lcp.fp("prefix","suffix"),Void,"",__LINE__); |
||
tester.stats();</ |
tester.stats();</syntaxhighlight> |
||
The fp (partial application) method is used to delay running lcp until the tester actually tests. |
The fp (partial application) method is used to delay running lcp until the tester actually tests. |
||
{{out}} |
{{out}} |