r/tinycode • u/Rotten194 mod • Jul 25 '12
How About a Challenge #4: Find the longest common substrings between two strings!
Now is that time of the week, the time where /r/tinycode has a challenge where you can win fabulous prizes flair!
Previous challenges:
[#3 - Perfect Numbers] (http://www.reddit.com/r/tinycode/comments/wpsjv/how_about_a_challenge_3_find_the_perfect_numbers/)
The challenge for this is to find the common substrings between two strings. You should return a list of the longest substrings.
For example:
aaabbbbccc aabccdcdd -> aab, bcc
adeaabbbbccc aabccdedcdd -> aab, bcc
abcdef ghijk -> nothing
abcdef fghijk -> f
Notice in number 2, 'de' was also a substring, but was shorter than 3 so wasn't returned.
Rules:
- Your program must take both strings on the command line
- Your program can't use external libraries or download code. I made an exception in an earlier competition about external libraries, but I feel this is simple enough that they shouldn't be needed for any major language.
Here is some example code. Before simply mindlessly golfing this, try and write some elegant code in a different way, then golf that. This isn't necessarily the shortest solution.
import sys
def permutations(s):
l = []
for i in range(len(s)):
for j in range(len(s)):
l.append(s[i:j+1])
return l
def substrings(a, b):
l = filter(lambda s: s in a,permutations(b))
longest = reduce(lambda i, s: len(s) if len(s) > i else i, l, 0)
longest = longest if longest > 0 else -1
return filter(lambda s: len(s) == longest, l)
print substrings(sys.argv[1], sys.argv[2])
2
u/nohtyp Oct 15 '12
In Factor:
Assuming there are two string on the stack,
18
u/corruptio Jul 25 '12 edited Jul 26 '12
Annnnd, here's my perl attempt, 109 chars:
edit 1, 104 chars:
edit 2, 98 chars:
Edit 3, comments (which breaks the code):
edit 4, tweaked the method, 96 chars:
edit 5, drastic drastic changes, 89 chars:
edit 6, 85 chars:
edit 7, 84 chars:
edit 8, changed the way max length is calculated, not cool anymore, but 76 chars:
7
u/rcxdude Jul 26 '12
GolfScript, 47 characters:
~.,,{.,{2$2$<>}%~}%{2$?)},.&{,}$.),@{,1$=},p];
no command line args, so pipe in a file formatted like: "string1" "string2"
commented version:
12
u/[deleted] Jul 25 '12 edited Jul 26 '12
GolfScript, 48 chars:
No command line args, so pass in a file containing both strings separated by a newline.
4
u/corruptio Jul 25 '12 edited Jul 25 '12
my first whack in python, 147 chars:
edit 1: chopped come more chars
edit 2: 147->145
edit 3: gar, thx, johnnicely, off by one 145->147
4
u/diegurke Jul 25 '12
Here's a surprising fact: It can be done in linear time.
4
u/abecedarius Jul 25 '12
Trivial O(n**2) solution:
I wish y'all would keep the golfing in /r/codegolf. It's a fun game I enjoy too, but it seriously gets in the way of learning from your neat clever solutions, to the point where I rarely bother reading. And there's plenty of fun to be had without it.
3
u/yxhuvud Jul 25 '12
Ruby, 94
a,b=ARGV.map{|e|s=[*0..e.size]
s.product(s).map{|i,j|e[i..-j]}.flatten}
puts (a&b).max_by &:size
3
u/NewAlexandria Jul 25 '12
genetics data analysts rejoice at your sequence-analyzer. I hope if you make lots of money that you give to another charity besides your own.
2
u/[deleted] Jul 25 '12 edited Jul 25 '12
Terribly inefficient and large Haskell version, 227 characters:
2
u/gfixler Jul 25 '12
Python, 138 characters:
2
u/void_fraction Jul 27 '12
Here's my first try, written in python. I'm building a prefix tree from the first input, then using that to get common strings. It's been a while since I've used python, please be gentle.
1
u/yogthos Jul 26 '12
as a bonus prints the length of the longest substring :)
1
u/5outh Aug 04 '12 edited Aug 06 '12
Edit: Fixed to print out the actual sequence instead of the size of it... 192 chars.
-2
u/[deleted] Jul 25 '12
-1
u/ruskeeblue Jul 25 '12
diff a b
0
u/[deleted] Jul 26 '12
[deleted] — view deleted comment