Greatest common substringShortest Longest Common Subsequence CodeDecompose a StringGiven a string find the substring which appears most oftenFind Patterns in StringsShortest Longest Common Subsequence CodeMaximal Substring ConstructionVisualize the greatest common divisorShortest Unique SubstringAs Easy As A-B-CFind the original string, without the repetition without the repetition in the middleThe Third String
What linear sensor for a keyboard?
Translation of Scottish 16th century church stained glass
Do the concepts of IP address and network interface not belong to the same layer?
Folder comparison
Can a significant change in incentives void an employment contract?
If a character with the Alert feat rolls a crit fail on their Perception check, are they surprised?
Is there a word to describe the feeling of being transfixed out of horror?
Why does Async/Await work properly when the loop is inside the async function and not the other way around?
What is the grammatical term for “‑ed” words like these?
Should I stop contributing to retirement accounts?
Does the Mind Blank spell prevent the target from being frightened?
Flux received by a negative charge
Could solar power be utilized and substitute coal in the 19th Century
Wrapping Cryptocurrencies for interoperability sake
Difference between -| and |- in TikZ
How must one send away the mother bird?
Is it possible to use .desktop files to open local pdf files on specific pages with a browser?
Varistor? Purpose and principle
Should I install hardwood flooring or cabinets first?
Find last 3 digits of this monster number
Have I saved too much for retirement so far?
My friend sent me a screenshot of a transaction hash, but when I search for it I find divergent data. What happened?
Why did the HMS Bounty go back to a time when whales are already rare?
Longest common substring in linear time
Greatest common substring
Shortest Longest Common Subsequence CodeDecompose a StringGiven a string find the substring which appears most oftenFind Patterns in StringsShortest Longest Common Subsequence CodeMaximal Substring ConstructionVisualize the greatest common divisorShortest Unique SubstringAs Easy As A-B-CFind the original string, without the repetition without the repetition in the middleThe Third String
$begingroup$
Create a program or function which takes a list of strings as input, and outputs the longest string that is a substring of all input strings. If there are several substrings of equal length, and no longer substring, output any one of them.
- This may mean outputting the empty string.
- If there are several valid outputs, you may output any one of them. You are not required to give consistent outpput for a given input so long as the output is always valid.
- There will always be at least one string in the input, but there might not be a non-empty string.
- All printable ASCII characters may appear in the input. You may assume those are the only characters that appear.
- You may take input or produce output by any of the default methods.
Standard loopholes aren't allowed.- This is code-golf - the fewer bytes of code, the better.
Test cases:
[Inputs] -> [Valid outputs (choose one)]
["hello", "'ello"] -> ["ello"]
["very", "much", "different"] -> [""]
["empty", "", "STRING"] -> [""]
["identical", "identical"] -> ["identical"]
["string", "stRIng"] -> ["st", "ng"]
["this one", "is a substring of this one"] -> ["this one"]
["just one"] -> ["just one"]
["", "", ""] -> [""]
["many outputs", "stuptuo ynam"] -> ["m", "a", "n", "y", " ", "o", "u", "t", "p", "s"]
["many inputs", "any inputs", "ny iii", "yanny"] -> ["ny"]
["%%not&", "ju&#st", "[&]alpha_numeric"] -> ["&"]
code-golf string subsequence
$endgroup$
add a comment |
$begingroup$
Create a program or function which takes a list of strings as input, and outputs the longest string that is a substring of all input strings. If there are several substrings of equal length, and no longer substring, output any one of them.
- This may mean outputting the empty string.
- If there are several valid outputs, you may output any one of them. You are not required to give consistent outpput for a given input so long as the output is always valid.
- There will always be at least one string in the input, but there might not be a non-empty string.
- All printable ASCII characters may appear in the input. You may assume those are the only characters that appear.
- You may take input or produce output by any of the default methods.
Standard loopholes aren't allowed.- This is code-golf - the fewer bytes of code, the better.
Test cases:
[Inputs] -> [Valid outputs (choose one)]
["hello", "'ello"] -> ["ello"]
["very", "much", "different"] -> [""]
["empty", "", "STRING"] -> [""]
["identical", "identical"] -> ["identical"]
["string", "stRIng"] -> ["st", "ng"]
["this one", "is a substring of this one"] -> ["this one"]
["just one"] -> ["just one"]
["", "", ""] -> [""]
["many outputs", "stuptuo ynam"] -> ["m", "a", "n", "y", " ", "o", "u", "t", "p", "s"]
["many inputs", "any inputs", "ny iii", "yanny"] -> ["ny"]
["%%not&", "ju&#st", "[&]alpha_numeric"] -> ["&"]
code-golf string subsequence
$endgroup$
$begingroup$
Possible duplicate
$endgroup$
– Adám
2 hours ago
$begingroup$
@Adám That question asks for the longest common subsequence, not substring.
$endgroup$
– Doorknob♦
2 hours ago
1
$begingroup$
Will the strings be only alphanumeric, or alphabetic, or only printable-ascii?
$endgroup$
– Embodiment of Ignorance
1 hour ago
$begingroup$
@EmbodimentofIgnorance All printable ASCII characters can appear in the input.
$endgroup$
– Sara J
1 hour ago
$begingroup$
@JoKing Yeah, it can. Apparently I'm too tired for this.
$endgroup$
– Sara J
24 mins ago
add a comment |
$begingroup$
Create a program or function which takes a list of strings as input, and outputs the longest string that is a substring of all input strings. If there are several substrings of equal length, and no longer substring, output any one of them.
- This may mean outputting the empty string.
- If there are several valid outputs, you may output any one of them. You are not required to give consistent outpput for a given input so long as the output is always valid.
- There will always be at least one string in the input, but there might not be a non-empty string.
- All printable ASCII characters may appear in the input. You may assume those are the only characters that appear.
- You may take input or produce output by any of the default methods.
Standard loopholes aren't allowed.- This is code-golf - the fewer bytes of code, the better.
Test cases:
[Inputs] -> [Valid outputs (choose one)]
["hello", "'ello"] -> ["ello"]
["very", "much", "different"] -> [""]
["empty", "", "STRING"] -> [""]
["identical", "identical"] -> ["identical"]
["string", "stRIng"] -> ["st", "ng"]
["this one", "is a substring of this one"] -> ["this one"]
["just one"] -> ["just one"]
["", "", ""] -> [""]
["many outputs", "stuptuo ynam"] -> ["m", "a", "n", "y", " ", "o", "u", "t", "p", "s"]
["many inputs", "any inputs", "ny iii", "yanny"] -> ["ny"]
["%%not&", "ju&#st", "[&]alpha_numeric"] -> ["&"]
code-golf string subsequence
$endgroup$
Create a program or function which takes a list of strings as input, and outputs the longest string that is a substring of all input strings. If there are several substrings of equal length, and no longer substring, output any one of them.
- This may mean outputting the empty string.
- If there are several valid outputs, you may output any one of them. You are not required to give consistent outpput for a given input so long as the output is always valid.
- There will always be at least one string in the input, but there might not be a non-empty string.
- All printable ASCII characters may appear in the input. You may assume those are the only characters that appear.
- You may take input or produce output by any of the default methods.
Standard loopholes aren't allowed.- This is code-golf - the fewer bytes of code, the better.
Test cases:
[Inputs] -> [Valid outputs (choose one)]
["hello", "'ello"] -> ["ello"]
["very", "much", "different"] -> [""]
["empty", "", "STRING"] -> [""]
["identical", "identical"] -> ["identical"]
["string", "stRIng"] -> ["st", "ng"]
["this one", "is a substring of this one"] -> ["this one"]
["just one"] -> ["just one"]
["", "", ""] -> [""]
["many outputs", "stuptuo ynam"] -> ["m", "a", "n", "y", " ", "o", "u", "t", "p", "s"]
["many inputs", "any inputs", "ny iii", "yanny"] -> ["ny"]
["%%not&", "ju&#st", "[&]alpha_numeric"] -> ["&"]
code-golf string subsequence
code-golf string subsequence
edited 6 mins ago
Sara J
asked 3 hours ago
Sara JSara J
1765
1765
$begingroup$
Possible duplicate
$endgroup$
– Adám
2 hours ago
$begingroup$
@Adám That question asks for the longest common subsequence, not substring.
$endgroup$
– Doorknob♦
2 hours ago
1
$begingroup$
Will the strings be only alphanumeric, or alphabetic, or only printable-ascii?
$endgroup$
– Embodiment of Ignorance
1 hour ago
$begingroup$
@EmbodimentofIgnorance All printable ASCII characters can appear in the input.
$endgroup$
– Sara J
1 hour ago
$begingroup$
@JoKing Yeah, it can. Apparently I'm too tired for this.
$endgroup$
– Sara J
24 mins ago
add a comment |
$begingroup$
Possible duplicate
$endgroup$
– Adám
2 hours ago
$begingroup$
@Adám That question asks for the longest common subsequence, not substring.
$endgroup$
– Doorknob♦
2 hours ago
1
$begingroup$
Will the strings be only alphanumeric, or alphabetic, or only printable-ascii?
$endgroup$
– Embodiment of Ignorance
1 hour ago
$begingroup$
@EmbodimentofIgnorance All printable ASCII characters can appear in the input.
$endgroup$
– Sara J
1 hour ago
$begingroup$
@JoKing Yeah, it can. Apparently I'm too tired for this.
$endgroup$
– Sara J
24 mins ago
$begingroup$
Possible duplicate
$endgroup$
– Adám
2 hours ago
$begingroup$
Possible duplicate
$endgroup$
– Adám
2 hours ago
$begingroup$
@Adám That question asks for the longest common subsequence, not substring.
$endgroup$
– Doorknob♦
2 hours ago
$begingroup$
@Adám That question asks for the longest common subsequence, not substring.
$endgroup$
– Doorknob♦
2 hours ago
1
1
$begingroup$
Will the strings be only alphanumeric, or alphabetic, or only printable-ascii?
$endgroup$
– Embodiment of Ignorance
1 hour ago
$begingroup$
Will the strings be only alphanumeric, or alphabetic, or only printable-ascii?
$endgroup$
– Embodiment of Ignorance
1 hour ago
$begingroup$
@EmbodimentofIgnorance All printable ASCII characters can appear in the input.
$endgroup$
– Sara J
1 hour ago
$begingroup$
@EmbodimentofIgnorance All printable ASCII characters can appear in the input.
$endgroup$
– Sara J
1 hour ago
$begingroup$
@JoKing Yeah, it can. Apparently I'm too tired for this.
$endgroup$
– Sara J
24 mins ago
$begingroup$
@JoKing Yeah, it can. Apparently I'm too tired for this.
$endgroup$
– Sara J
24 mins ago
add a comment |
8 Answers
8
active
oldest
votes
$begingroup$
Python 3, 137 bytes
def a(b):c=[[d[f:e]for e in range(len(d)+1)for f in range(e+1)]for d in b];return max([i for i in c[0]if all(i in j for j in c)],key=len)
Try it online!
New contributor
$endgroup$
$begingroup$
You may want to use single spaces as indentation instead of 4 that seems to shave more than 100 bytes.
$endgroup$
– Shieru Asakoto
2 hours ago
$begingroup$
@ShieruAsakoto Oops yeah.
$endgroup$
– Artemis Fowl
2 hours ago
$begingroup$
@JoKing tio.run/…
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
@JoKing The one currently in my answer is fine for all the test cases.
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
Right, here's a fixed version of the 135 byte program
$endgroup$
– Jo King
1 hour ago
add a comment |
$begingroup$
Jelly, 12 bytes
Ẇ€œ&/LÐṀḢ¹L?
Try it online!
Last four bytes are there because of the requirement to only output one answer.
$endgroup$
add a comment |
$begingroup$
Brachylog (v2), 3 bytes
sᵛw
Try it online!
Full program. Input from standard input (as a JSON-style list of strings), output to standard output.
Explanation
sᵛw
s Find a substring
ᵛ of every element of the input; the same one for each
w and output it.
Tiebreak order here is set by the s
, favouring the longest substring (the secondary tiebreak doesn't matter, but IIRC it's position within the first element of the input).
Brachylog's s
doesn't return empty substrings, so we need a bit of a trick to get around that: instead of making a function submission (which is what's normally done), we write a full program, outputting to standard output. That way, if there's a common substring, we just output it, and we're done. If there isn't a common substring, the program errors out – but it still prints nothing to standard output, thus it outputs the null string as intended.
$endgroup$
add a comment |
$begingroup$
Perl 6, 62 bytes
~sort(-*.comb,keys [∩] .map(*.comb[^*X.. ^*+1]>>.join))[0]
Try it online!
I'm a little annoyed the Perl 6 can't do set operations on lists of lists, which is why there's an extra .comb
and >>
in there. Another annoying thing is that max
can't take an function for how to compare items, meaning I have to user sort
instead.
$endgroup$
add a comment |
$begingroup$
Japt v2.0a0, 24 bytes
mã c f@eøXÃr@XÊ>YÊ?X:Y}P
This is a mess. Why isn't there a max function for arrays in Japt?
Try it online!
$endgroup$
add a comment |
$begingroup$
JavaScript (Node.js), 106 bytes
This assumes presence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.indexOf(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
JavaScript (Node.js), 114 105 bytes
This assumes absence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.search(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
Probably still golfable.
$endgroup$
add a comment |
$begingroup$
Zsh, 126 bytes
for l in $@
a=
for i in 0..$[$#l**2]
a+=($l[1+i/$#l,1+i%$#l])
b=($$b-$a:*a)
for i in $b
(($#x<$#i))&&x=$i
<<<$x
Try it online!
We read all possible substrings into $a
, and then intersect the common elements of $a
and $b
. The construct $b-$a
will only substitue $a
on the first iteration: Even if $b
is empty (no common strings), it is still set.
for l in $@;
a= # empty a
for i in 0..$[$#l**2]; # compound double loop using div/mod
a+=( $l[1+i/$#l,1+i%$#l] ) # append to a all possible substrings of the given line
b=( $$b-$a:*a )
# $b-$a # if b is unset substitute $a
# $ :*a # take common elements of $b-$a and $a
# b=( ) # set b to those elements
for i in $b; # for every common substring
(( $#x < $#i ))&&x=$i # if the current word is longer, use it
<<<$x # print to stdout
New contributor
$endgroup$
add a comment |
$begingroup$
Python 2, 103 bytes
lambda b:max(reduce(set.__and__,[d[f:e]for e in range(len(d)+2)for f in range(e)for d in b]),key=len)
Try it online!
This is an anonymous lambda that transforms each element into the set of all substrings, then reduce
s it by set intersection (set.__and__
) and then returns the max
element by len
gth.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f182134%2fgreatest-common-substring%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
8 Answers
8
active
oldest
votes
8 Answers
8
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Python 3, 137 bytes
def a(b):c=[[d[f:e]for e in range(len(d)+1)for f in range(e+1)]for d in b];return max([i for i in c[0]if all(i in j for j in c)],key=len)
Try it online!
New contributor
$endgroup$
$begingroup$
You may want to use single spaces as indentation instead of 4 that seems to shave more than 100 bytes.
$endgroup$
– Shieru Asakoto
2 hours ago
$begingroup$
@ShieruAsakoto Oops yeah.
$endgroup$
– Artemis Fowl
2 hours ago
$begingroup$
@JoKing tio.run/…
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
@JoKing The one currently in my answer is fine for all the test cases.
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
Right, here's a fixed version of the 135 byte program
$endgroup$
– Jo King
1 hour ago
add a comment |
$begingroup$
Python 3, 137 bytes
def a(b):c=[[d[f:e]for e in range(len(d)+1)for f in range(e+1)]for d in b];return max([i for i in c[0]if all(i in j for j in c)],key=len)
Try it online!
New contributor
$endgroup$
$begingroup$
You may want to use single spaces as indentation instead of 4 that seems to shave more than 100 bytes.
$endgroup$
– Shieru Asakoto
2 hours ago
$begingroup$
@ShieruAsakoto Oops yeah.
$endgroup$
– Artemis Fowl
2 hours ago
$begingroup$
@JoKing tio.run/…
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
@JoKing The one currently in my answer is fine for all the test cases.
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
Right, here's a fixed version of the 135 byte program
$endgroup$
– Jo King
1 hour ago
add a comment |
$begingroup$
Python 3, 137 bytes
def a(b):c=[[d[f:e]for e in range(len(d)+1)for f in range(e+1)]for d in b];return max([i for i in c[0]if all(i in j for j in c)],key=len)
Try it online!
New contributor
$endgroup$
Python 3, 137 bytes
def a(b):c=[[d[f:e]for e in range(len(d)+1)for f in range(e+1)]for d in b];return max([i for i in c[0]if all(i in j for j in c)],key=len)
Try it online!
New contributor
edited 1 hour ago
New contributor
answered 2 hours ago
Artemis FowlArtemis Fowl
1114
1114
New contributor
New contributor
$begingroup$
You may want to use single spaces as indentation instead of 4 that seems to shave more than 100 bytes.
$endgroup$
– Shieru Asakoto
2 hours ago
$begingroup$
@ShieruAsakoto Oops yeah.
$endgroup$
– Artemis Fowl
2 hours ago
$begingroup$
@JoKing tio.run/…
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
@JoKing The one currently in my answer is fine for all the test cases.
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
Right, here's a fixed version of the 135 byte program
$endgroup$
– Jo King
1 hour ago
add a comment |
$begingroup$
You may want to use single spaces as indentation instead of 4 that seems to shave more than 100 bytes.
$endgroup$
– Shieru Asakoto
2 hours ago
$begingroup$
@ShieruAsakoto Oops yeah.
$endgroup$
– Artemis Fowl
2 hours ago
$begingroup$
@JoKing tio.run/…
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
@JoKing The one currently in my answer is fine for all the test cases.
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
Right, here's a fixed version of the 135 byte program
$endgroup$
– Jo King
1 hour ago
$begingroup$
You may want to use single spaces as indentation instead of 4 that seems to shave more than 100 bytes.
$endgroup$
– Shieru Asakoto
2 hours ago
$begingroup$
You may want to use single spaces as indentation instead of 4 that seems to shave more than 100 bytes.
$endgroup$
– Shieru Asakoto
2 hours ago
$begingroup$
@ShieruAsakoto Oops yeah.
$endgroup$
– Artemis Fowl
2 hours ago
$begingroup$
@ShieruAsakoto Oops yeah.
$endgroup$
– Artemis Fowl
2 hours ago
$begingroup$
@JoKing tio.run/…
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
@JoKing tio.run/…
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
@JoKing The one currently in my answer is fine for all the test cases.
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
@JoKing The one currently in my answer is fine for all the test cases.
$endgroup$
– Artemis Fowl
1 hour ago
$begingroup$
Right, here's a fixed version of the 135 byte program
$endgroup$
– Jo King
1 hour ago
$begingroup$
Right, here's a fixed version of the 135 byte program
$endgroup$
– Jo King
1 hour ago
add a comment |
$begingroup$
Jelly, 12 bytes
Ẇ€œ&/LÐṀḢ¹L?
Try it online!
Last four bytes are there because of the requirement to only output one answer.
$endgroup$
add a comment |
$begingroup$
Jelly, 12 bytes
Ẇ€œ&/LÐṀḢ¹L?
Try it online!
Last four bytes are there because of the requirement to only output one answer.
$endgroup$
add a comment |
$begingroup$
Jelly, 12 bytes
Ẇ€œ&/LÐṀḢ¹L?
Try it online!
Last four bytes are there because of the requirement to only output one answer.
$endgroup$
Jelly, 12 bytes
Ẇ€œ&/LÐṀḢ¹L?
Try it online!
Last four bytes are there because of the requirement to only output one answer.
answered 2 hours ago
Nick KennedyNick Kennedy
92147
92147
add a comment |
add a comment |
$begingroup$
Brachylog (v2), 3 bytes
sᵛw
Try it online!
Full program. Input from standard input (as a JSON-style list of strings), output to standard output.
Explanation
sᵛw
s Find a substring
ᵛ of every element of the input; the same one for each
w and output it.
Tiebreak order here is set by the s
, favouring the longest substring (the secondary tiebreak doesn't matter, but IIRC it's position within the first element of the input).
Brachylog's s
doesn't return empty substrings, so we need a bit of a trick to get around that: instead of making a function submission (which is what's normally done), we write a full program, outputting to standard output. That way, if there's a common substring, we just output it, and we're done. If there isn't a common substring, the program errors out – but it still prints nothing to standard output, thus it outputs the null string as intended.
$endgroup$
add a comment |
$begingroup$
Brachylog (v2), 3 bytes
sᵛw
Try it online!
Full program. Input from standard input (as a JSON-style list of strings), output to standard output.
Explanation
sᵛw
s Find a substring
ᵛ of every element of the input; the same one for each
w and output it.
Tiebreak order here is set by the s
, favouring the longest substring (the secondary tiebreak doesn't matter, but IIRC it's position within the first element of the input).
Brachylog's s
doesn't return empty substrings, so we need a bit of a trick to get around that: instead of making a function submission (which is what's normally done), we write a full program, outputting to standard output. That way, if there's a common substring, we just output it, and we're done. If there isn't a common substring, the program errors out – but it still prints nothing to standard output, thus it outputs the null string as intended.
$endgroup$
add a comment |
$begingroup$
Brachylog (v2), 3 bytes
sᵛw
Try it online!
Full program. Input from standard input (as a JSON-style list of strings), output to standard output.
Explanation
sᵛw
s Find a substring
ᵛ of every element of the input; the same one for each
w and output it.
Tiebreak order here is set by the s
, favouring the longest substring (the secondary tiebreak doesn't matter, but IIRC it's position within the first element of the input).
Brachylog's s
doesn't return empty substrings, so we need a bit of a trick to get around that: instead of making a function submission (which is what's normally done), we write a full program, outputting to standard output. That way, if there's a common substring, we just output it, and we're done. If there isn't a common substring, the program errors out – but it still prints nothing to standard output, thus it outputs the null string as intended.
$endgroup$
Brachylog (v2), 3 bytes
sᵛw
Try it online!
Full program. Input from standard input (as a JSON-style list of strings), output to standard output.
Explanation
sᵛw
s Find a substring
ᵛ of every element of the input; the same one for each
w and output it.
Tiebreak order here is set by the s
, favouring the longest substring (the secondary tiebreak doesn't matter, but IIRC it's position within the first element of the input).
Brachylog's s
doesn't return empty substrings, so we need a bit of a trick to get around that: instead of making a function submission (which is what's normally done), we write a full program, outputting to standard output. That way, if there's a common substring, we just output it, and we're done. If there isn't a common substring, the program errors out – but it still prints nothing to standard output, thus it outputs the null string as intended.
answered 1 hour ago
community wiki
ais523
add a comment |
add a comment |
$begingroup$
Perl 6, 62 bytes
~sort(-*.comb,keys [∩] .map(*.comb[^*X.. ^*+1]>>.join))[0]
Try it online!
I'm a little annoyed the Perl 6 can't do set operations on lists of lists, which is why there's an extra .comb
and >>
in there. Another annoying thing is that max
can't take an function for how to compare items, meaning I have to user sort
instead.
$endgroup$
add a comment |
$begingroup$
Perl 6, 62 bytes
~sort(-*.comb,keys [∩] .map(*.comb[^*X.. ^*+1]>>.join))[0]
Try it online!
I'm a little annoyed the Perl 6 can't do set operations on lists of lists, which is why there's an extra .comb
and >>
in there. Another annoying thing is that max
can't take an function for how to compare items, meaning I have to user sort
instead.
$endgroup$
add a comment |
$begingroup$
Perl 6, 62 bytes
~sort(-*.comb,keys [∩] .map(*.comb[^*X.. ^*+1]>>.join))[0]
Try it online!
I'm a little annoyed the Perl 6 can't do set operations on lists of lists, which is why there's an extra .comb
and >>
in there. Another annoying thing is that max
can't take an function for how to compare items, meaning I have to user sort
instead.
$endgroup$
Perl 6, 62 bytes
~sort(-*.comb,keys [∩] .map(*.comb[^*X.. ^*+1]>>.join))[0]
Try it online!
I'm a little annoyed the Perl 6 can't do set operations on lists of lists, which is why there's an extra .comb
and >>
in there. Another annoying thing is that max
can't take an function for how to compare items, meaning I have to user sort
instead.
answered 1 hour ago
Jo KingJo King
25.3k361129
25.3k361129
add a comment |
add a comment |
$begingroup$
Japt v2.0a0, 24 bytes
mã c f@eøXÃr@XÊ>YÊ?X:Y}P
This is a mess. Why isn't there a max function for arrays in Japt?
Try it online!
$endgroup$
add a comment |
$begingroup$
Japt v2.0a0, 24 bytes
mã c f@eøXÃr@XÊ>YÊ?X:Y}P
This is a mess. Why isn't there a max function for arrays in Japt?
Try it online!
$endgroup$
add a comment |
$begingroup$
Japt v2.0a0, 24 bytes
mã c f@eøXÃr@XÊ>YÊ?X:Y}P
This is a mess. Why isn't there a max function for arrays in Japt?
Try it online!
$endgroup$
Japt v2.0a0, 24 bytes
mã c f@eøXÃr@XÊ>YÊ?X:Y}P
This is a mess. Why isn't there a max function for arrays in Japt?
Try it online!
answered 59 mins ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,138125
2,138125
add a comment |
add a comment |
$begingroup$
JavaScript (Node.js), 106 bytes
This assumes presence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.indexOf(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
JavaScript (Node.js), 114 105 bytes
This assumes absence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.search(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
Probably still golfable.
$endgroup$
add a comment |
$begingroup$
JavaScript (Node.js), 106 bytes
This assumes presence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.indexOf(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
JavaScript (Node.js), 114 105 bytes
This assumes absence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.search(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
Probably still golfable.
$endgroup$
add a comment |
$begingroup$
JavaScript (Node.js), 106 bytes
This assumes presence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.indexOf(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
JavaScript (Node.js), 114 105 bytes
This assumes absence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.search(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
Probably still golfable.
$endgroup$
JavaScript (Node.js), 106 bytes
This assumes presence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.indexOf(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
JavaScript (Node.js), 114 105 bytes
This assumes absence of regex special characters.
a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.search(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)
Try it online!
Probably still golfable.
edited 50 mins ago
answered 2 hours ago
Shieru AsakotoShieru Asakoto
2,750317
2,750317
add a comment |
add a comment |
$begingroup$
Zsh, 126 bytes
for l in $@
a=
for i in 0..$[$#l**2]
a+=($l[1+i/$#l,1+i%$#l])
b=($$b-$a:*a)
for i in $b
(($#x<$#i))&&x=$i
<<<$x
Try it online!
We read all possible substrings into $a
, and then intersect the common elements of $a
and $b
. The construct $b-$a
will only substitue $a
on the first iteration: Even if $b
is empty (no common strings), it is still set.
for l in $@;
a= # empty a
for i in 0..$[$#l**2]; # compound double loop using div/mod
a+=( $l[1+i/$#l,1+i%$#l] ) # append to a all possible substrings of the given line
b=( $$b-$a:*a )
# $b-$a # if b is unset substitute $a
# $ :*a # take common elements of $b-$a and $a
# b=( ) # set b to those elements
for i in $b; # for every common substring
(( $#x < $#i ))&&x=$i # if the current word is longer, use it
<<<$x # print to stdout
New contributor
$endgroup$
add a comment |
$begingroup$
Zsh, 126 bytes
for l in $@
a=
for i in 0..$[$#l**2]
a+=($l[1+i/$#l,1+i%$#l])
b=($$b-$a:*a)
for i in $b
(($#x<$#i))&&x=$i
<<<$x
Try it online!
We read all possible substrings into $a
, and then intersect the common elements of $a
and $b
. The construct $b-$a
will only substitue $a
on the first iteration: Even if $b
is empty (no common strings), it is still set.
for l in $@;
a= # empty a
for i in 0..$[$#l**2]; # compound double loop using div/mod
a+=( $l[1+i/$#l,1+i%$#l] ) # append to a all possible substrings of the given line
b=( $$b-$a:*a )
# $b-$a # if b is unset substitute $a
# $ :*a # take common elements of $b-$a and $a
# b=( ) # set b to those elements
for i in $b; # for every common substring
(( $#x < $#i ))&&x=$i # if the current word is longer, use it
<<<$x # print to stdout
New contributor
$endgroup$
add a comment |
$begingroup$
Zsh, 126 bytes
for l in $@
a=
for i in 0..$[$#l**2]
a+=($l[1+i/$#l,1+i%$#l])
b=($$b-$a:*a)
for i in $b
(($#x<$#i))&&x=$i
<<<$x
Try it online!
We read all possible substrings into $a
, and then intersect the common elements of $a
and $b
. The construct $b-$a
will only substitue $a
on the first iteration: Even if $b
is empty (no common strings), it is still set.
for l in $@;
a= # empty a
for i in 0..$[$#l**2]; # compound double loop using div/mod
a+=( $l[1+i/$#l,1+i%$#l] ) # append to a all possible substrings of the given line
b=( $$b-$a:*a )
# $b-$a # if b is unset substitute $a
# $ :*a # take common elements of $b-$a and $a
# b=( ) # set b to those elements
for i in $b; # for every common substring
(( $#x < $#i ))&&x=$i # if the current word is longer, use it
<<<$x # print to stdout
New contributor
$endgroup$
Zsh, 126 bytes
for l in $@
a=
for i in 0..$[$#l**2]
a+=($l[1+i/$#l,1+i%$#l])
b=($$b-$a:*a)
for i in $b
(($#x<$#i))&&x=$i
<<<$x
Try it online!
We read all possible substrings into $a
, and then intersect the common elements of $a
and $b
. The construct $b-$a
will only substitue $a
on the first iteration: Even if $b
is empty (no common strings), it is still set.
for l in $@;
a= # empty a
for i in 0..$[$#l**2]; # compound double loop using div/mod
a+=( $l[1+i/$#l,1+i%$#l] ) # append to a all possible substrings of the given line
b=( $$b-$a:*a )
# $b-$a # if b is unset substitute $a
# $ :*a # take common elements of $b-$a and $a
# b=( ) # set b to those elements
for i in $b; # for every common substring
(( $#x < $#i ))&&x=$i # if the current word is longer, use it
<<<$x # print to stdout
New contributor
edited 43 mins ago
New contributor
answered 52 mins ago
GammaFunctionGammaFunction
615
615
New contributor
New contributor
add a comment |
add a comment |
$begingroup$
Python 2, 103 bytes
lambda b:max(reduce(set.__and__,[d[f:e]for e in range(len(d)+2)for f in range(e)for d in b]),key=len)
Try it online!
This is an anonymous lambda that transforms each element into the set of all substrings, then reduce
s it by set intersection (set.__and__
) and then returns the max
element by len
gth.
$endgroup$
add a comment |
$begingroup$
Python 2, 103 bytes
lambda b:max(reduce(set.__and__,[d[f:e]for e in range(len(d)+2)for f in range(e)for d in b]),key=len)
Try it online!
This is an anonymous lambda that transforms each element into the set of all substrings, then reduce
s it by set intersection (set.__and__
) and then returns the max
element by len
gth.
$endgroup$
add a comment |
$begingroup$
Python 2, 103 bytes
lambda b:max(reduce(set.__and__,[d[f:e]for e in range(len(d)+2)for f in range(e)for d in b]),key=len)
Try it online!
This is an anonymous lambda that transforms each element into the set of all substrings, then reduce
s it by set intersection (set.__and__
) and then returns the max
element by len
gth.
$endgroup$
Python 2, 103 bytes
lambda b:max(reduce(set.__and__,[d[f:e]for e in range(len(d)+2)for f in range(e)for d in b]),key=len)
Try it online!
This is an anonymous lambda that transforms each element into the set of all substrings, then reduce
s it by set intersection (set.__and__
) and then returns the max
element by len
gth.
edited 39 mins ago
answered 51 mins ago
Jo KingJo King
25.3k361129
25.3k361129
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f182134%2fgreatest-common-substring%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Possible duplicate
$endgroup$
– Adám
2 hours ago
$begingroup$
@Adám That question asks for the longest common subsequence, not substring.
$endgroup$
– Doorknob♦
2 hours ago
1
$begingroup$
Will the strings be only alphanumeric, or alphabetic, or only printable-ascii?
$endgroup$
– Embodiment of Ignorance
1 hour ago
$begingroup$
@EmbodimentofIgnorance All printable ASCII characters can appear in the input.
$endgroup$
– Sara J
1 hour ago
$begingroup$
@JoKing Yeah, it can. Apparently I'm too tired for this.
$endgroup$
– Sara J
24 mins ago