37
\$\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
    Commented 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
    Commented 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
    Commented 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\$ Commented Nov 5, 2015 at 16:08
  • 2
    \$\begingroup\$ Can it return the length? \$\endgroup\$
    – S.S. Anne
    Commented Mar 13, 2020 at 17:45

73 Answers 73

1
\$\begingroup\$

Clojure/ClojureScript, 51

(defn f[[a & b][c & d]](if(= a c)(str a(f b d))""))

Pretty straightforward. Unfortunately the spaces around the parameter destructuring are necessary (that's the [a & b] stuff). Not the shortest but I beat some other answers in languages that like to brag about their terseness so I'll post it.

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

ed, sed, 19 bytes

ex, 18 bytes

vim, 20 bytes

s/\(.*\).* \1.*/\1/

This also works with ex/vi (heirloom ex 050325), and the trailing slash is not required.

Oddly, this should work in vim, but mysteriously fails. It works if I add another unused capture group, something which should not change the semantics of the regex at all:

s/\v(.*)(.* \1.*)/\1

It fails and gives garbage answers in nvi and the results are downright mysterious:

:1
global glossary
:s/\(.*\)\(.*\) \1\(.*\)/\1{\2,\3}/
global{,ry}

NOTE: This expects the words on the current [last in the file] line [or every line for the sed script] separated by a space, and containing no space. To operate on every line in ex/vim, add % to the beginning. I don't think I'm the only program here to have constraints like these.

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

Python 2, 50 bytes

for a,b in zip(*input()):print(1/0if a!=b else a),

Input

The input is taken as two strings:

"global", "glossary"

Output

The output is each character followed by a space; which, hopefully, isn't a problem. However, if it is, I'll edit my answer.

g l o 
\$\endgroup\$
9
  • \$\begingroup\$ I'm pretty sure this is invalid; the spec clearly gave the output format as a string without spaces. \$\endgroup\$
    – lirtosiast
    Commented Nov 4, 2015 at 1:15
  • \$\begingroup\$ Well yes, but the input was also given in the format "global" , "glossary" (two separate strings).. How many other answers follow that to the letter? @ThomasKwa \$\endgroup\$
    – Zach Gates
    Commented Nov 4, 2015 at 1:18
  • \$\begingroup\$ "takes two strings" is the language used by OP; usually when something like that is mentioned without any qualifiers, it refers to one of our default I/O, which means we can take one string from the command line and one from STDIN, or an array of two strings, or whatever else follows those rules. \$\endgroup\$
    – lirtosiast
    Commented Nov 4, 2015 at 1:24
  • \$\begingroup\$ I think you're taking my answer a bit too seriously. This is just a fun submission and my best attempt at beating a built-in. If OP doesn't like the output format, so be it; I'll remove my answer. @ThomasKwa \$\endgroup\$
    – Zach Gates
    Commented Nov 4, 2015 at 1:28
  • \$\begingroup\$ How about print(exit()if a!=b else a,end='')? I don't know if that'll work or not, but it might \$\endgroup\$
    – Beta Decay
    Commented Nov 4, 2015 at 6:53
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
    Commented 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
    Commented Nov 5, 2015 at 9:50
  • \$\begingroup\$ Fixed! Thanks for pointing out. \$\endgroup\$
    – corvus_192
    Commented 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\$

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\$
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 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
    Commented Dec 12, 2016 at 14:53
  • \$\begingroup\$ see here \$\endgroup\$
    – Xanderhall
    Commented Dec 12, 2016 at 15:10
  • \$\begingroup\$ @Xanderhall In the description it states "Write a program that takes 2 strings as input.." \$\endgroup\$ Commented 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
    Commented 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\$ Commented Dec 14, 2016 at 14:33
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
    Commented Jul 3, 2018 at 15:06
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\$

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\$
1
\$\begingroup\$

C, 59 bytes

main(int c,char**a){while(*a[1]==*a[2]++)putchar(*a[1]++);}

Input from the command-line arguments.

Note - will overrun after printing the final null character if the input strings are identical.

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

Zsh, 46 bytes

until [[ $1 = ${2%$~s}* ]] {s+=?;}
<<<${2%$~s}

Try it online!

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

Vyxal, a, 5 4 bytes

R÷ġṘ

Try it Online!

Explained

R÷ġṘ
R÷   # vectorise reverse over the input (wrapped in an array by the -a flag) and push contents onto the stack
  ġ  # Push the greatest common suffix
   Ṙ # and reverse it to get the prefix
\$\endgroup\$
1
\$\begingroup\$

V (vim), 41 40 bytes

qqhYp$x@qq@qo<esc>j$@qo<esc>:%!awk 'a[$0]++'
jdG

Try it online!

No regex.

Takes the strings on two separate lines. The awk command is from here.

Once the matching prefixes are found, we delete everything except the first line.

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

05AB1E, 10 bytes

.ps.p©å®Ï¤

Try it online!

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

Thunno 2, 6 bytes

Z€ạġhị

Attempt This Online!

Explanation

Z€ạġhị  # Implicit input
Z       # Zip them together
 €      # To each inner pair:
  ạ     #  Check if they're equal
   ġ    # Group consecutive items
    h   # Get the first group
     ị  # Corresponding filter
        # Implicit output
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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