Daily Programming Challenge

Write a program that returns the largest common string between two arguments.

Examples:
$./main aweasdf op9-0awsdf
==> "sdf"

$./main qxbn322r pv22rqx reqxetc
==>qx

Other urls found in this thread:

youtube.com/watch?v=GLg_wp0IXoI&
youtube.com/watch?v=vZa0Yh6e7dw
pastebin.com/a14bgM5E
twitter.com/NSFWRedditGif

static String common( String str1, String str2) {
String largest = null;

for( int i=0; i < str1.length(); ++i) {
for( int j=i+1; j < str1.length(); ++j) {
if( !str2.contains(str1.substring(i, j)))
break;

if( largest == null || largest.length() < j - i)
largest = str1.substring(i, j);
}
}
return largest;
}
static String common( List strings) {
String largest = null;

if( strings == null || strings.isEmpty()) return null;
if( strings.size() == 1) return strings.get(0);

String str1 = strings.get(0);

for( int i=0; i < str1.length(); ++i) {
for( int j=i+1; j < str1.length(); ++j) {
boolean bad = false;
for( String str2 : strings) {
if( str2 == str1) continue;

if( !str2.contains(str1.substring(i, j))) {
bad = true;
break;
}
}
if( bad) break;

if( largest == null || largest.length() < j - i)
largest = str1.substring(i, j);
}
}
return largest;
}

>actually doing OP's homework
top cuck

woops, forgot how substring indexes. Should be

*meant to say "two or more"

01 MAX-LEN PIC 9999 COMP.
01 WS-IX1 PIC 9999 COMP.
01 WS-IX2 PIC 9999 COMP.
01 WK-LEN PIC 9999 COMP.
01 WS-LOC1 PIC 9999 COMP.
01 WS-LOC2 PIC 9999 COMP.
01 WS-FLAG PIC X.
88 NO-DIFFERENCE-FOUND VALUE 'N'.
88 DIFFERENCE-FOUND VALUE 'Y'.

MOVE ZERO TO MAX-LEN.
PERFORM VARYING WS-IX1 FROM 1 BY 1 UNTIL WS-IX1 > WS-LEN1
PERFORM VARYING WS-IX2 FROM 1 BY 1 UNTIL WS-IX2 > WS-LEN2
SET NO-DIFFERENCE-FOUND TO TRUE
PERFORM VARYING WK-LEN FROM MAX-LEN BY 1 UNTIL
WS-IX1 + WK-LEN > WS-LEN1 OR
WS-IX2 + WK-LEN > WS-LEN2 OR
DIFFERENCE-FOUND
IF WS-TEXT1(WS-IX1 : WK-LEN + 1) = WS-TEXT2(WS-IX2 : WK-LEN + 1)
COMPUTE MAX-LEN = WK-LEN + 1
MOVE WS-IX1 TO WS-LOC1
MOVE WS-IX2 TO WS-LOC2
ELSE
SET DIFFERENCE-FOUND TO TRUE
END-IF
END-PERFORM
END-PERFORM
END-PERFORM.

It's actually your daily homework :)

use List::Util qw/reduce/;
print reduce{length($a)

($_)=sort{length $blength $a}"$ARGV[0]\0$ARGV[1]"=~/(.+)(?=.*\0.*\1)/g;print
All right. Here's the version without reduce.

C:\>perl cs.pl aweaseeeeesdf op9-0aewsdf
sdf
C:\>perl cs.pl aweaseeeeesdf op9-0aeeeeeeeeeeeeeeeeeewsdf
eeeee
C:\>

Whose fang is this?

Which dialect of COBOL is that? Very nice!

the anime girls fang

Sakurano probably

This is probably a really stupid way to do it, but I didn't feel like tracking the largest substring "found so far" logic because I'm not very good at it.

char *largest_common(char *str1, char *str2)
{
unsigned len = strlen(str1);
unsigned i, j;
for (i = len; i > 0; --i) /* query len */
{
for (j = 0; i + j

Chinese cartoon girl number four.

I'll solve this tomorrow and keep you guys posted

it's not even that hard

Perl wins again with shortest code to complete the task. The best!

i cant even fucking read it

Too bad for you.

christ
this looks like what an autistic child would imagine regex to be

It works.

Plus the actual regular expression I use is extremely simple.

No need to fear the unknown, user.

kirino an shit

It's not Kirino, it's that stupid new vampire girl from that one anime drawn by the same artist.

It would be infinitely better if it was Kirino, amirite?

don't slip off on me now thread.

Page 10 save rave!

I know, but it was late and I was tired. Now that it's the morning -- here you go.

>two arguments
>$./main qxbn322r pv22rqx reqxetc

what language is this? I thought that char meant it was a one character string, and other strings had to be declared str

this is C

and you're correct, char can only hold a single character byte, but an array of chars lets you hold strings of arbitrary length

Very nice. Here's your up(You).

i don't wanna rewrite my solution to use va_args because that's dumb

I rewrote my solution to be 90% more efficient!
There's no point in searching for larger substrings within smaller ones.

char *largest_common(const char *str1, const char *str2)
{
unsigned l1 = strlen(str1), l2 = strlen(str2);
const char *sm = (l1 < l2) ? str1 : str2;
const char *lg = (l2 > l1) ? str2 : str1;
unsigned len = strlen(sm);
unsigned i, j;
for (i = len; i > 0; --i) /* query length */
{
for (j = 0; i + j

So if I get this right,
>./strcmp abcdef abcdxef ef1234 123efxx
should output "ef"?
This seems like a difficult problem and everyone is ignoring it so far by making their solution only take two arguments.

Given texts T1, T2, ..., Tn on the alphabet A, we want the maximal word W such that W is a subword of each Ti.

1. Build a suffix tree of the text "T1#1T2#2...Tn" (where #i are symbols not in A).
2. Mark all the inner nodes that, for each Ti, have at least one leaf that started in Ti.
3. Pick one of the marked nodes that's at a maximal distance from the root.

Conceptually, you only need to check the first and shortest string given, and then part it out by checking all possible substrings within it.
Then sequentially check if that substring exists in all the other strings.
If it does, you have a match.

You got me fired up so I went ahead and rewrote it to take an arbitrary number of arguments.
char *largest_common_n(const char **str, unsigned args)
{
unsigned i, j, k, len;
char **arr = (char **) malloc(sizeof(char *) * args);
for (i = 0; i < args; i++) /* mutable array copy */
arr[i] = (char *) str[i];
char *sm = *arr, *ret = NULL;
for (i = 0; i < args; i++) /* find smallest */
{
if (strlen(arr[i]) > strlen(sm))
{
char *tmp = sm;
sm = arr[i];
arr[i] = tmp;
}
}
len = strlen(sm);
for (i = len; i > 0; --i) /* query length */
{
for (j = 0; i + j

; --- Finds longest common substring in n strings ---
; requires 8086 cpu and about 1kB free memory
; assemble with fasm

org 0x100
use16
cld
xor bx, bx
xor ch, ch
mov cl, [0x80]
mov di, 0x82
@@: mov al, ' '
mov dx, cx
repne scasb
sub dx, cx
mov ax, di
sub ax, dx
dec dx
test dx, dx
jz @b
push ax
push dx
inc bl
jcxz @f
jmp @b
@@: cmp bl, 1
jbe error_input
mov bp, sp
mov cx, [bp]
.ret_too_long:
mov si, [bp+2]
.ret_next_substr:
mov di, bx
shl di, 2
.next_str:
sub di, 4
test di, di
jz .found
cmp [bp+di], cx
jb .too_long
push di
push cx
mov cx, [bp+di]
mov di, [bp+di+2]
.search_again:
mov al, [si]
repne scasb
jne .next_substr
dec di
inc cx
pop ax
push ax
cmp cx, ax
jb .next_substr
xchg cx, ax
push di
push si
repe cmpsb
pop si
pop di
je @f
mov cx, ax
dec cx
inc di
jmp .search_again
@@: pop cx
pop di
jmp .next_str
.next_substr:
pop cx
pop di
inc si
mov di, si
add di, cx
mov ax, [bp+2]
add ax, [bp]
cmp di, ax
jbe .ret_next_substr
.too_long:
dec cx
test cx, cx
jnz .ret_too_long
.found:
mov dx, si
add si, cx
mov byte [si], '$'
mov ah, 0x09
int 0x21
mov ax, 0x4c00
int 0x21

error_input:
mov dx, err_input
mov ah, 0x09
int 0x21
mov ax, 0x4cff
int 0x21
err_input db "Usage: STRCMP str0 str1 [str2 ... strn]$"
That turned out to be easier than I expected.

string challenge(const string& first, const string& second)
{
vector possible;
for (int i = 0; i < first.size(); ++i) {
for (int j = 0; j < second.size(); ++j) {
string newitem = "";
int iter = 0;
if (first[i] == second[j]) {
while (first[i + iter] == second[j + iter]) {
newitem += first[i + iter];
if (i + iter == first.size()) break;
iter++;
}
possible.push_back(newitem);
}
}
}
std::sort(possible.begin(), possible.end(), [](string a, string b) {
return a.size() > b.size();
});
cout

System.out.println(common( Arrays.asList(new String[]{"abcdef", "abcdxef", "ef1234", "123efxx"})));
Result
ef
Works for me.

>casting malloc in C

>implying it's not done everywhere

>sizeof(char)

fucking hell

Is there a problem?

sizeof(char) is absolutely and everywhere always exactly 1

#include
#include
#include

auto find_common(auto strings)
{
auto a = strings.back();
strings.pop_back();
auto begin = 0;
auto length = a.length();

next_substr:
auto b = a.substr(begin, length);
for (auto s : strings)
if (s.find(b) == std::string::npos)
{
if (++begin + length > a.length())
{
begin = 0;
--length;
}
goto next_substr;
}
return b;
}

int main(int argc, char** argv)
{
std::vector input { };
for(int i = 1; i < argc; ++i) input.emplace_back(argv[i]);
std::cout

ditch string
ditch vector
ditch iostream

It's good practice regardless. It's not like it compiles any different.

C++ is such a disgusting language.

>malloc(sizeof(char) * i + 1);
is the same as
>malloc(i + 1);
the compiler may or may not optimize it, depends
but if the compiler doesn't it compiles different
in the first one you get the size of a char first and then calculate it

it's not good practice
I don't know who told you that
but it's not good practice to sizeof(char)

see also he used labels and goto in c++
no one fucking does that

his post is the incarnation of everything why everybody thinks c++ is a bad language

The compiler "may or may not" optimize a sizeof into a literal and then optimize 1 * (int)x into just x? Man, why are all C++ "enthusiasts" such paranoid ignoramuses?

Yes, it's always good practice to do sizeof(type) into malloc. Because you might change the type at some point in the future. I know you enthusiasts have a hard-on for brevity and in consciously putting pitfalls into your code and jacking off to the fact that you never step on them, but it's bad design.

listening to childhood anime OP and ED

I just can't program with all this nostalgia bottled up inside ;_;

>cant even think of how to start this problem
oh well i planned on being a C# monkey anyways

>sizeof(char) is absolutely and everywhere always exactly 1
No it's not, its some times 1L some times 1UL and some times 1ULL.

You're forgetting the type, it's a size_t.

you will never be able to be a smart programmer unless you take off your clothes and put knee socks on, user

>goto
what else would you use? I'd like to see you try rewriting the same function without it.

btw same thing with iterators
auto find_common(auto strings)
{
auto a = strings.back();
strings.pop_back();
auto begin = a.cbegin();
auto end = a.cend();

next_substr:
for (const auto& s : strings)
if (*std::search(s.cbegin(), s.cend(), begin, end) != *begin)
{
if (++begin == a.cend()) break;
if (end >= a.cend())
{
end -= (begin - a.cbegin());
begin = a.cbegin();
}
else ++end;
goto next_substr;
}
return std::string { begin, end };
}

It was this
youtube.com/watch?v=GLg_wp0IXoI&

or

youtube.com/watch?v=vZa0Yh6e7dw

Wasn't it user?

...

Scala:
object Substr extends App {
println(args(0).zip(args(1)).takeWhile(s => s._1 == s._2).unzip._1.mkString)
}

I'm sure there's a shorter solution
import Data.List
common a b = maximumBy (\x y -> length x `compare` length y)
$ intersect (strings a) (strings b)
where strings = takeWhile (/="") . iterate (drop 1)

why would you use goto in lieu of a loop structure?
goto should only be used to escape from multi-level loops.

Excuse my autism
private string SearchStrings(string str1, string str2)
{
string str3 = string.Empty;
int length = 0;
for (int i = 0; i < str1.Length; i++)
{
for (int j = 0; j < str2.Length; j++)
{
if (str1[i] == str2[j])
{
int localLength = 1;
int k = i + 1;
for (int l = j + 1; k < str1.Length && l < str2.Length; k++, l++)
{
if (str1[k] == str2[l])
{
localLength++;
}
}
string localString = str1.Substring(i, localLength);
if (localLength > length)
{
length = localLength;
str3 = localString;
}
}
}
}
return str3;
}

I only see like 3 solutions that actually do what the OP asked for, which is finding the common substring in all the strings provided, not just 2.

function stringCommon(str1,str2){
var largest=undefined;
for(i=0;i

>which is finding the common substring in all the strings provided, not just 2.

>Write a program that returns the largest common string between two arguments.
>returns the largest common string between two arguments.
>between two arguments.
>two

this.

challenge dropped

> compare "heyy" "youu"
> *** Exception: Prelude.foldr1: empty list

l2r idiot

Without goto, it would be:
auto find_common(auto strings)
{
auto a = strings.back();
strings.pop_back();
auto begin = a.cbegin();
auto end = a.cend();

bool found;
do
{
found = true;
for (const auto& s : strings)
if (std::search(s.cbegin(), s.cend(), begin, end) != s.cend())
{
if (++begin == a.cend()) break;
if (end == a.cend())
{
end -= (begin - a.cbegin());
begin = a.cbegin();
}
else ++end;
found = false;
break;
}
}
while (!found);

return std::string { begin, end };
}
So there's a multi-level loop. Using flags as control flow just for the sake of avoiding goto is way worse than a single goto, imo.

see

stop making me want to learn x86 assembly

import Data.List

f :: String -> String -> [String]
f xs ys
| xs == [] = []
| ys == [] = []
| xs `isInfixOf` ys = [xs]
| otherwise = g $ (f (tail xs) ys) ++ (f (init xs) ys)
where
g zs = [z | z

I dropped in some comments for you. so now you have no reason not to.
>>>pastebin.com/a14bgM5E