34
\$\begingroup\$

Write a program that takes 2 strings as input, and returns the longest common prefix. This is , so the answer with the shortest amount of bytes wins.

Test Case 1:

"global" , "glossary"
"glo"


Test Case 2:

"department" , "depart"
"depart"

Test Case 3:

"glove", "dove"
""
\$\endgroup\$
7
  • 3
    \$\begingroup\$ Do you want a complete programs that inputs from STDIN and prints to STDOUT, or are functions OK? \$\endgroup\$
    – xnor
    Nov 3, 2015 at 19:35
  • 3
    \$\begingroup\$ Can we assume the input won't have newlines? Which characters will the input have? \$\endgroup\$
    – Downgoat
    Nov 3, 2015 at 23:59
  • 7
    \$\begingroup\$ General note: People using a regex based solution should not copy other people's regex answers without testing them yourself; this does not work in all regex engines. In particular, it gives different (both incorrect) answers in nvi and vim. \$\endgroup\$
    – Random832
    Nov 4, 2015 at 16:38
  • 2
    \$\begingroup\$ All of the examples given are in lowercase, but do we need to worry about case sensitivity? For example, should global and GLOSSARY return glo or ''? \$\endgroup\$ Nov 5, 2015 at 16:08
  • 2
    \$\begingroup\$ Can it return the length? \$\endgroup\$
    – S.S. Anne
    Mar 13, 2020 at 17:45

69 Answers 69

1
\$\begingroup\$

TeaScript, 16 bytes 20

xf»l¦y[i]?1:b=0)

Takes each input separated by a space.

\$\endgroup\$
1
\$\begingroup\$

PHP, 52 bytes

Not spectacular but does the job:

$a=$argv;while($a[1][$i]==$a[2][$i])echo$a[1][$i++];

Takes two command line arguments:

php prefix.php department depart
\$\endgroup\$
1
  • \$\begingroup\$ PHP7 lets you save another byte while(($a=$argv)[1][$i]==$a[2][$i])echo$a[1][$i++]; - Another PHP7 only solution (and best I could come up with @ 50 bytes) <?=substr(($a=$argv)[1],0,strspn($a[1]^$a[2],~ÿ)); - Make sure your editor is in ascii mode, it's important the ~ÿ does not get converted to unicode. \$\endgroup\$
    – Leigh
    Nov 27, 2015 at 14:22
1
\$\begingroup\$

MATLAB, 63 bytes

Defines a function that accepts 2 strings as input.

function f(a,b),c=1;try,while a(c)==b(c),c=c+1;end,end,a(1:c-1)

Had to include a try-statement for those cases where a would be a is a longer string than b.

  • If we have the freedom to always supply the shorter string to a, then 8 bytes can be removed.
  • If it is allowed to define a and b in the workspace, then another 16 bytes can be removed.
\$\endgroup\$
1
\$\begingroup\$

R, 130 bytes

substr(x[1],1,which.max(apply(do.call(rbind,lapply(strsplit(x,''),`length<-`,nchar(x[1]))),2,function(i)!length(unique(i))==1))-1)

Usage:

x <- c('bubblegum','bubbafish')
\$\endgroup\$
1
\$\begingroup\$

Scala, 90 bytes

object S extends App{print(args(0)zip args(1)takeWhile{case(a,b)=>a==b}map(_._1)mkString)}

It takes to Strings as arguments and outputs to stdout.

\$\endgroup\$
2
  • \$\begingroup\$ This won't print a string to STDOUT, but a Vector[Tuple2[Char,Char]] \$\endgroup\$
    – Jacob
    Nov 5, 2015 at 9:50
  • \$\begingroup\$ Fixed! Thanks for pointing out. \$\endgroup\$
    – corvus_192
    Nov 5, 2015 at 19:31
1
\$\begingroup\$

brainfuck, 91 bytes

+[>>,>++++[<-------->-]<]<<[<<]>+[>>++++[>++++++++<-],]<[<]>>-<[>>[<+>>-<-]+>[<->,]<[<.,]>]

Requires an interpreter that either allows negative positions on the tape or wraps if you < from 0. Also requires , to return 0 every time you use it after input runs out. (In my experience these are both the most common behaviour.) Takes input as two words separated by a space.

This was a lot easier than I expected it to be! Usually I decide to write a brainfuck program and end up devoting quite a bit of time to it, but this one played nice. My first idea ended up working well and being rather short, especially for brainfuck.

This works by getting the entire first word and storing the characters in every second cell, then weaving in the second word (e.g. gglloosbsaalr y). Then, for each pair of characters a and b, it copies a a cell to the left and simultaneously replaces b with b-a. The cell a used to be in becomes NOT (b-a). If that's true, a is printed and the loop continues to the next set of characters. Otherwise, nothing is printed and the loop terminates.

I only used two real golfing tricks in this program. The first was combining two unrelated loops while gathering input. The first word is initially stored with each of its bytes subtracted by 32, so that space becomes 0 and the loop can end. Rather than adding 32 to each of those bytes and then getting the second word, the program does both at the same time. The second trick I used was abuse of , when I know the input is empty. The idiomatic way of setting a cell to 0 is [-]. However, if you know that the program has already read the entire input, most interpreters will let you try to get a byte of input anyway and set the current cell to NUL, or 0. I use this twice in my program, saving 4 bytes.

Ungolfed:

+[>>,>++++[<-------->-]<]          get first word (minus 32 at each byte)

<<[<<]>                            go back to start

+[>>++++[>++++++++<-],]            get second word and add 32 to each byte of
                                   first word

<[<]>>-<                           go back to start and clean up a little bit

[                                  main loop

  >>[<+>>-<-]                        subtract letter from second word from
                                     letter of first word 

  +>[<->,]<                          logical NOT the result

  [<.,]>                             if the result is 1: print the letter
                                     else: the loop dies and execution is
                                     terminated 

]
\$\endgroup\$
1
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 25 chars / 39 bytes

ô⟦ï0]Ă⇀$≔ï1[_]?1:ï1=0)ø⬯)

Try it here (Firefox only).

It barely looks like ES6.

\$\endgroup\$
1
\$\begingroup\$

MUMPS, 54 bytes

t(a,b) f i=$L(a):-1:0 s p=$E(a,1,i) q:p=$E(b,1,i)
    q p

Typically primitive stuff - it just compares successively-shorter prefixes of the strings until it hits a match.

\$\endgroup\$
1
\$\begingroup\$

Javascript: 67 Bytes

(a,b)=>{for(i=0;i<a.length;i++){if(a[i]!=b[i])return a.slice(0,i)}}
\$\endgroup\$
1
\$\begingroup\$

><>, 37 bytes

i:0( ?\
4*=?\$>1+{:8
+[r]\$1
?!;o>:{=

Try it online!

Input is via STDIN, and is expected without quotes, separated by a space. For example, global glossary.

After the input is read, the characters up to and including the space are reversed and pushed back onto the stack. For example, if the input were global glossary, the stack would be glossary labolg. The stack is then rotated to the left one step at a time. If the top two chars are the same, output. Otherwise, end.

\$\endgroup\$
1
\$\begingroup\$

C# 147 146

string l(string a,string b){var s="";for(int i=0;i<Math.Min(a.Length,b.Length);i++){if(a[i]==b[i])s+=a[i];else return a.Substring(0,i);}return s;}

Readable and ungolfed version

    string longestPrefix(string a, string b)
    {
        var s = "";
        for (int i = 0; i < Math.Min(a.Length, b.Length); i++)
        {
            if (a[i] == b[i]) s+=a[i];
            else return a.Substring(0, i);
        }

        return s;
    }

How it works:

It loops until characters on the same index do not match. Every character that matches is added to s string, otherwise return a new string from zero index to current iteration.

\$\endgroup\$
1
\$\begingroup\$

Brainfuck, 61 bytes

+
[
  ,[<+> >+<-]
  ++++[>--------<-]
  >
]
<<[<]
<+
[
  ,[>+>-<<-]
  >>[<]
  <[.>]
  <
]

Expects two words separated by a space.

Try it online.

\$\endgroup\$
1
\$\begingroup\$

Java 8, 76 bytes

(a,b)->{String m="";for(int i=0;i<a.length&&a[i]==b[i];)m+=a[i++];return m;}

Lambda that takes 2 char[] arguments. Loops through until the letters stop matching or we match them all, appending them to a blank string as it goes.

\$\endgroup\$
1
\$\begingroup\$

Scala, 85 83 77 bytes

def f(a:String,b:String)=a zip b takeWhile(a=>a._1==a._2) map(_._1) mkString

for example,

f("global" , "glossary")

returns

glo
\$\endgroup\$
1
  • \$\begingroup\$ (edited: the return type is made explicit by the last "mkString" invocation) \$\endgroup\$
    – Leonardo
    Jul 3, 2018 at 15:06
1
\$\begingroup\$

Jelly, 6 bytes

¹Ƥ€f/Ṫ

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Rust, 75 bytes

|a,b|a.chars().zip(b.chars()).take_while(|(a,b)|a==b).map(|v|v.0).collect()

Try it online!

Does unnecessary heap allocation for the result (idiomatic Rust code would return &str here as opposed to String), but it works so whatever. It's not like it matters.

This iterates over string characters as long as characters match and then collects matched characters into a String.

\$\endgroup\$
1
\$\begingroup\$

K (oK) / K4, 21 19 bytes

Solution:

(*x)@&&\=/(#,/x)$x:

Try it online!

Explanation:

Pad strings to combined length of the strings, check for equality, find matching indices, take minimum over resulting list, and index into first element of original input at these indices.

(*x)@&&\=/(#,/x)$x: / the solution
                 x: / save input as x
                $   / pad
          (    )    / do together
            ,/x     / flatten (,/) x
           #        / count (returns length)
        =/          / compare, equals (=) over (/)
      &\            / mins, min (&) scan (\)
     &              / indices where true
    @               / index into
(  )                / do this together
 *x                 / first (*) x
\$\endgroup\$
1
\$\begingroup\$

Kotlin, 55 bytes

Not-Lame Edition! (no builtin)

{zip(it).takeWhile{(a,b)->a==b}.fold(""){a,(f,_)->a+f}}

{zip(it)                                                 // zip first string with second
        .takeWhile{(a,b)->a==b}                          // take pairs while chars are equal
                               .fold(""){a,(f,_)->a+f}}  // fold into string

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Japt -h, 6 bytes

®å+Ãrf

Try it

\$\endgroup\$
1
\$\begingroup\$

Husk, 6 4 bytes

→¤nḣ

Try it online!

-2 bytes from Dominic Van essen.

\$\endgroup\$
1
1
\$\begingroup\$

x86-16 machine code, 6 bytes

00000000  56 A6 74 FD 4E C3                                 V.t.N.

Callable function.

Expects [SI] = address of first string, [DI] = address of second string.

Outputs as: Top of stack = start of memory slice, SI = end of memory slice (like the slice in Python).

Disassembly:

56            PUSH    SI    ; Store original SI onto stack
A6      LOOP: CMPSB         ; Compare [SI++] with [DI++]
74 FD         JZ      LOOP  ; If they're equal, jump to tag 'LOOP'
4E            DEC     SI    ; -- SI
C3            RET           ; Return to caller

Example run

-d 0100
0B4A:0100  56 A6 74 FD 4E C3 00 00-00 00 00 00 00 00 00 00   V.t.N...........
0B4A:0110  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
0B4A:0120  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
0B4A:0130  67 6C 6F 62 61 6C 00 00-00 00 00 00 00 00 00 00   global..........
0B4A:0140  67 6C 6F 73 73 61 72 79-00 00 00 00 00 00 00 00   glossary........
0B4A:0150  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
0B4A:0160  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
0B4A:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-r
AX=0000  BX=0000  CX=0000  DX=0000  SP=FFEA  BP=0000  SI=0130  DI=0140
DS=0B4A  ES=0B4A  SS=0B4A  CS=0B4A  IP=0100   NV UP EI PL NZ NA PO NC
0B4A:0100 56            PUSH    SI
-t

AX=0000  BX=0000  CX=0000  DX=0000  SP=FFE8  BP=0000  SI=0130  DI=0140
DS=0B4A  ES=0B4A  SS=0B4A  CS=0B4A  IP=0101   NV UP EI PL NZ NA PO NC
0B4A:0101 A6            CMPSB
...
-t

AX=0000  BX=0000  CX=0000  DX=0000  SP=FFE8  BP=0000  SI=0133  DI=0144
DS=0B4A  ES=0B4A  SS=0B4A  CS=0B4A  IP=0105   NV UP EI PL NZ NA PE CY
0B4A:0105 C3            RET
-d ss:ffe0
0B4A:FFE0  00 00 00 00 30 01 4A 0B-AE 05 30 01 30 01 00 00   ....0.J...0.0...
0B4A:FFF0  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-rsp
SP FFEA
:
-
\$\endgroup\$
0
\$\begingroup\$

K, 45 bytes

{*|(*v)@{&y~'x}.#[&/#:'v;]'v:{#[;x]'1+!#x}'x}

Takes input as a 2-element list.

\$\endgroup\$
0
\$\begingroup\$

Swift, 34 bytes

import UIKit "global".commonPrefixWith("glossary")

But with Swift 2 it is actually more like: "global".commonPrefixWithString("glossary",options:.CaseInsensitiveSearch)

\$\endgroup\$
0
\$\begingroup\$

C#, 112 bytes

class P{static void Main(string[]a){try{for(int i=0;a[0][i]==a[1][i];)System.Console.Write(a[0][i++]);}catch{}}}

Newlines and indentation for clarity:

class P{
    static void Main(string[]a){
        try{
            for(int i=0;a[0][i]==a[1][i];)
                System.Console.Write(a[0][i++]);
        }
        catch{}
    }
}
\$\endgroup\$
0
\$\begingroup\$

Minkolang 0.10, 21 bytes

(od" "=,)x(0gdo=?.O1)

Expects input as two words, space-separated, like so: department depart. Try it here.

Explanation

(od" "=,)      Loops through input until a space is encountered
x              Dumps extraneous space
(0gdo=   1)    Loops through second word and compares letters
      ?.O      Halts if two letters are not equal, outputs them otherwise
\$\endgroup\$
0
\$\begingroup\$

pb, 105 bytes

^w[B!32]{>}>w[B!0]{t[B]vb[1]<[X]w[B!0]{>}b[T]w[B!1]{>}b[0]^>}v<[X]<t[0]w[T=0]{>t[B]^t[T-B]v}w[B!0]{b[0]>}

Takes two words separated by a single space. (I can save a byte by using a tab instead but that feels like cheating.)

In pb, the area that can be written to is thought of as a 2D space, with (0, 0) in the upper left. Additionally, input is initially kept at Y=-1. This program copies the second word of the input to Y=0 (starting at (0, 0)). Then, each letter is compared to the letter immediately above it until one is found that doesn't match. The rest of the word is erased and the desired output is already on the canvas so it's printed when execution halts.

Ungolfed:

^w[B!32]{>}>       # Go to the first letter of the second word
w[B!0]{            # For each letter in the second word:
    t[B]             # Save the letter to T
    vb[1]            # Put a flag below that letter so it can be found later
    <[X]w[B!0]{>}    # Go to the first empty space on Y=0
    b[T]             # Write the contents of T
    w[B!1]{>}b[0]    # Go back to the flag and erase it
    ^>               # Restart loop from next letter
}

v<[X]<             # Go to (-1, 0)
t[0]               # Set T to 0
w[T=0]{            # While T is 0:
    >t[B]            # Save the next letter of the second word to T
    ^t[T-B]v         # Subtract the equivalent letter of the first word from T

    # If they were the same, T is 0 and the loop continues.
}

w[B!0]{b[0]>}      # Erase the rest of the second word
\$\endgroup\$
0
\$\begingroup\$

Ruby, 44 characters

->a,b{i=0;i+=1while a[i]&&a[i]==b[i];a[0,i]}

Sample run:

2.1.5 :001 > ->a,b{i=0;i+=1while a[i]&&a[i]==b[i];a[0,i]}["global , "glossary"]
 => "glo"

2.1.5 :002 > ->a,b{i=0;i+=1while a[i]&&a[i]==b[i];a[0,i]}["department", "depart"]
 => "depart"

2.1.5 :003 > ->a,b{i=0;i+=1while a[i]&&a[i]==b[i];a[0,i]}["glove", "dove"]
 => ""
\$\endgroup\$
0
0
\$\begingroup\$

Dyalog APL, 12 bytes

{⊥⍨⌽=⌿↑⍵}↑∊

That's two bytes less than the previous APL solution!

The overall function is , which takes n elements (characters) from the flattened () argument, where n is the result of applying the function {⊥⍨⌽=⌿↑⍵} to the argument:

↑⍵ convert list of strings to table (padding with spaces to form rectangle)
=⌿ compare down (columns) giving boolean list
reverse
⊥⍨ count trailing trues*


*Literally it is a mixed-base to base-10 conversion, using the boolean list as both number and base:

⊥⍨0 1 0 1 1 is the same as 0 1 0 1 1⊥⍨0 1 0 1 1 which is 0×(0×1×0×1×1) 1×(1×0×1×1) 0×(0×1×1) 1×(1×1) + 1×(1) which again is two (the number of trailing 1s).

\$\endgroup\$
0
\$\begingroup\$

PHP, 49 bytes

<?=substr($t=$argv[1],0,strspn($t^$argv[2],"\0"));

Replace \0 with the actual byte.

\$\endgroup\$
0
\$\begingroup\$

Java 7, 145 bytes

class M{public static void main(String[]a){for(char i=0,c;i<a[0].length();){c=a[0].charAt(i);if(c!=a[1].charAt(i++))break;System.out.print(c);}}}

Those pesky program-requirements instead of function..

Ungolfed:

class M{
  public static void main(String[] a){
    for(char i = 0, c; i < a[0].length(); ){
      c = a[0].charAt(i);
      if(c != a[1].charAt(i++)){
        break;
      }
      System.out.print(c);
    }
  }
}

Try it here.

\$\endgroup\$
6
  • \$\begingroup\$ Pretty sure you're allowed to assume 'programs or functions' unless full program is specified by OP \$\endgroup\$
    – Xanderhall
    Dec 12, 2016 at 14:53
  • \$\begingroup\$ see here \$\endgroup\$
    – Xanderhall
    Dec 12, 2016 at 15:10
  • \$\begingroup\$ @Xanderhall In the description it states "Write a program that takes 2 strings as input.." \$\endgroup\$ Dec 12, 2016 at 18:38
  • \$\begingroup\$ If you'd looked at the link I posted, you'd see that the community consensus is that the default for a challenge is "program or function". \$\endgroup\$
    – Xanderhall
    Dec 14, 2016 at 13:10
  • \$\begingroup\$ @Xanderhall I know the default is program or function, but in this question the OP states it should be a program. The question rules overrules that default rule... \$\endgroup\$ Dec 14, 2016 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.