30
\$\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\$
  • 1
    \$\begingroup\$ Another good test case is "aca", "aba". \$\endgroup\$ – Morgan Thrapp Nov 3 '15 at 19:00
  • 2
    \$\begingroup\$ Do you want a complete programs that inputs from STDIN and prints to STDOUT, or are functions OK? \$\endgroup\$ – xnor Nov 3 '15 at 19:35
  • 2
    \$\begingroup\$ Can we assume the input won't have newlines? Which characters will the input have? \$\endgroup\$ – Downgoat Nov 3 '15 at 23:59
  • 5
    \$\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 '15 at 16:38
  • 1
    \$\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\$ – AdmBorkBork Nov 5 '15 at 16:08

60 Answers 60

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\$
  • \$\begingroup\$ This won't print a string to STDOUT, but a Vector[Tuple2[Char,Char]] \$\endgroup\$ – Jacob Nov 5 '15 at 9:50
  • \$\begingroup\$ Fixed! Thanks for pointing out. \$\endgroup\$ – corvus_192 Nov 5 '15 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\$
  • \$\begingroup\$ (edited: the return type is made explicit by the last "mkString" invocation) \$\endgroup\$ – Leonardo Jul 3 '18 at 15:06
0
\$\begingroup\$

K, 45 bytes

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

Takes input as a 2-element list.

\$\endgroup\$
0
\$\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\$
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
\$\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\$
  • \$\begingroup\$ Pretty sure you're allowed to assume 'programs or functions' unless full program is specified by OP \$\endgroup\$ – Xanderhall Dec 12 '16 at 14:53
  • \$\begingroup\$ see here \$\endgroup\$ – Xanderhall Dec 12 '16 at 15:10
  • \$\begingroup\$ @Xanderhall In the description it states "Write a program that takes 2 strings as input.." \$\endgroup\$ – Kevin Cruijssen Dec 12 '16 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 '16 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\$ – Kevin Cruijssen Dec 14 '16 at 14:33
0
\$\begingroup\$

05AB1E, 10 bytes (non-competing)

.ps.p©å®Ï¤

Try it online!

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

Regex, 12 bytes

(^.*).*$\n\1

each input string is separate line. https://regex101.com/r/bTf1ud/1

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

Powershell + Regex, 48 bytes

$m=$args-join"`n"-match"(^.*).*`n\1";$Matches[1]

one line input strings only.

Powershell pure, 58 56 bytes

param($a,$b)for($i=0;$a[$i]-eq$b[$i]){$c+=$a[$i++]};"$c"

Test script:

$f = {
param($a,$b)for($i=0;$a[$i]-eq$b[$i]){$c+=$a[$i++]};"$c"
}

"glo" -eq (&$f "global" "glossary")
"depart" -eq (&$f "department"  "depart")
"" -eq (&$f "glove" "dove")

Output:

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

C# (Visual C# Compiler), 62 bytes

(a,b)=>Concat(a.Zip(b,(x,y)=>x==y?x:'$').TakeWhile(x=>x!='$'))

Try it online!

Zip! This byte count includes only the lambda expression, and some necessary using static directives are not counted.

It is assumed that no word will contain the magical char value $ (otherwise program may fail). Can use \0 instead (but that is longer to type).

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

Jelly, 6 bytes

¹Ƥ€f/Ṫ

Try it online!

\$\endgroup\$
0
\$\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\$
0
\$\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\$

Java, 152 bytes

String a="aa",b="ab";char[]c=a.toCharArray(),d=b.toCharArray();int e=0,f=Math.min(c.length,d.length);for(;e<f&&c[e]==d[e];e++);return new String(c,0,e);
\$\endgroup\$
  • 1
    \$\begingroup\$ What's your language and score? \$\endgroup\$ – Hand-E-Food Nov 4 '15 at 22:37

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.