#Brachylog , 23 bytes

:1foh.,{,.[A:B]hs?'~sB}

Works on the old Java transpiler. Expects the two strings in a list as input, unifies the output with the substring. If no substring is found, returns false.

Unfortunately I have not yet coded the subset built-in in the new Prolog transpiler.

###Explanation

:1f Find all bindings which satisfy predicate 1 with that binding as input and
 with the Input of the main predicate as output.
 oh., Order that list of bindings, and unify the output with the first one.
{
 ,.[A:B] Unify the output with the list [A,B]
 hs? Unify the input with a subset of A
 '~sB Check that no subset of B can be unified with the input
 }

Brachylog , 23 bytes

:1foh.,{,.[A:B]hs?'~sB}

Works on the old Java transpiler. Expects the two strings in a list as input, unifies the output with the substring. If no substring is found, returns false.

Unfortunately I have not yet coded the subset built-in in the new Prolog transpiler.

Explanation

:1f Find all bindings which satisfy predicate 1 with that binding as input and
 with the Input of the main predicate as output.
 oh., Order that list of bindings, and unify the output with the first one.
{
 ,.[A:B] Unify the output with the list [A,B]
 hs? Unify the input with a subset of A
 '~sB Check that no subset of B can be unified with the input
 }

#Brachylog, 23 bytes

:1foh.,{,.[A:B]hs?'~sB}

Works on the old Java transpiler. Expects the two strings in a list as input, unifies the output with the substring. If no substring is found, returns false.

Unfortunately I have not yet coded the subset built-in in the new Prolog transpiler yet.

###Explanation

:1f Find all bindings which satisfy predicate 1 with that binding as input and
 with the Input of the main predicate as output.
 oh., Order that list of bindings, and unify the output with the first one.
{
 ,.[A:B] Unify the output with the list [A,B]
 hs? Unify the input with a subset of A
 '~sB Check that no subset of B can be unified with the input
 }

#Brachylog, 23 bytes

:1foh.,{,.[A:B]hs?'~sB}

Works on the old Java transpiler. Expects the two strings in a list as input, unifies the output with the substring. If no substring is found, returns false.

Unfortunately I have not yet coded the subset built-in in the new Prolog transpiler.

###Explanation

:1f Find all bindings which satisfy predicate 1 with that binding as input and
 with the Input of the main predicate as output.
 oh., Order that list of bindings, and unify the output with the first one.
{
 ,.[A:B] Unify the output with the list [A,B]
 hs? Unify the input with a subset of A
 '~sB Check that no subset of B can be unified with the input
 }

#Brachylog, 23 bytes

:1foh.,{,.[A:B]hs?'~sB}

Works on the old Java transpiler. Expects the two strings as a list as input, unifies the output with the substring. If no substring is found, returns false.

Unfortunately I have not yet coded the subset built-in in the new Prolog transpiler yet.

###Explanation

pending...

#Brachylog, 23 bytes

:1foh.,{,.[A:B]hs?'~sB}

Works on the old Java transpiler. Expects the two strings in a list as input, unifies the output with the substring. If no substring is found, returns false.

Unfortunately I have not yet coded the subset built-in in the new Prolog transpiler yet.

###Explanation

:1f Find all bindings which satisfy predicate 1 with that binding as input and
 with the Input of the main predicate as output.
 oh., Order that list of bindings, and unify the output with the first one.
{
 ,.[A:B] Unify the output with the list [A,B]
 hs? Unify the input with a subset of A
 '~sB Check that no subset of B can be unified with the input
 }