|
|
Post by goulstem on Apr 26, 2017 22:49:55 GMT
Your job is to create a function that takes in a string, and outputs the largest duplicate substring within that string.
[ Examples ] -
- [Input]: "BillyBobJoeBob went to the store one day to talk to his cousin BobbyJoeBob" --> [Output]: "JoeBob"
- [Input]: "If you mess with the cat again the consequences will be catastrophic" --> [Output]: "cat" or "the"
*Please format your answer with the language and number of characters, prior to the solution in code block. *Must be case sensitive |
|
|
|
Post by thebayou on Apr 27, 2017 22:53:44 GMT
Finished in Python, but not yet uglified/micro-optimized. You can find the solution on repl.it here. |
|
|
|
Post by fumeisencho on Apr 28, 2017 0:09:04 GMT
Lua, 151 chars. BTW for your first input string, the highest duplicate substring would be "to", not "joebob".
edit: it is only 151 chars, post formatting added extra newlines.
function d(s)
w=""
h=0
for x in s:gmatch("%w+") do
m=0
for y in s:gmatch("%w+") do
m=(y==x and m+1 or m)
end
if m>h then
h=m
w=x
end
end
return w
end
|
|
|
|
Post by Bit on Apr 28, 2017 0:13:04 GMT
fumeisenchoFixed the OP myself, thanks for pointing that out. Also, nice solution, but you should likely try and minify("uglify") it to make it much shorter.
|
|
|
|
Post by fumeisencho on Apr 28, 2017 0:31:18 GMT
I did.
|
|
|
|
Post by Bit on Apr 28, 2017 0:45:53 GMT
Oh lol, my bad, didn't read that you formatted it again afterwards
|
|
|
|
Post by cntkillme on Apr 28, 2017 0:53:13 GMT
No it was right to begin with, you just did the challenge wrong.
|
|
|
|
Post by Bit on Apr 28, 2017 1:38:11 GMT
Wellthen, I'm just going to slowly get out right now and go back to work...
|
|
|
|
Post by Josh on Apr 28, 2017 6:23:39 GMT
cntkillme is correct unfortunately, I've changed the post back to its original state.
|
|
|
|
Post by thebayou on Apr 28, 2017 17:23:14 GMT
The Lua solution is wrong; there's no support for more than one most common substring.
|
|
|
|
Post by goulstem on Apr 28, 2017 19:50:24 GMT
BTW for your first input string, the highest duplicate substring would be "to", not "joebob". The challenge is to find the largest duplicate substring, not the substring with the highest amount of replications. Although "to" repeats more times, "joebob" would be a larger duplicate. |
|
|
|
Post by goulstem on Apr 28, 2017 19:52:28 GMT
Finished in Python, but not yet uglified/micro-optimized. You can find the solution on repl.it here. That's really close  I love the code, but the challenge is for the function to find the largest common substring itself - not to have any other input to go off of. I can't declare this challenge solved yet. muahahaha it continues |
|
|
|
Post by cntkillme on May 4, 2017 6:34:38 GMT
In your 2nd example, there is actually a possible third solution: "e c"
Ok I'll start out, but I'm sure it could be much shorter:
function f(s)
z={}for i=1,#s do
k=''for j=1,#s do
a=s:sub(i,i)b=s:sub(j,j)if a==b then
k=k..a
i=i+1
elseif #k>0 then
z[#z+1]=k
k=''end
end
end
table.sort(z,function(a,b)return#a>#b end)return z[1]end199 characters. This is insanely high but whatever.
Edit: just looked at it and realized a small error. I should be checking if the length of k is positive, not if the length of s is positive (has been fixed).
Edit 2: used my brain and made it 33 characters shorter and more efficient:
function f(s)
g=''for i=1,#s do
k=''
for j=1,#s do
a=s:sub(i,i)b=s:sub(j,j)if a==b then
k=k..a
i=i+1
elseif #k>0 then
g=#k>#g and k or g
k=''end
end
end
return g
end166 characters.
If you want to disregard the first line and last 2 lines, you end up with 138 characters. You can end up with 144 characters if you just want to output it too (warn(g)).
|
|
I love the code, but the challenge is for the function to find the largest common substring itself - not to have any other input to go off of.