Check if a string is a shuffle of twins Explanation

Two strings can be shuffled by interspersing their letters to form a new string, much like two piles of cards can be shuffled to form a single pile.

For example, the strings HELLO and WORLD can be shuffled to form HWEOLRLLOD, or HEWORLLLDO, or perhaps simply HELLOWORLD. 

It is not a shuffle if the original order of letters is not preserved. For example, the D in WORLD cannot ever appear before the R after being shuffled. This means that EHLLOWRDLO, for instance, is not a shuffle of HELLO and WORLD, even though it contains all the original letters.

A string is a shuffle of twins if it can be formed by shuffling two identical strings. For example, ABACBDECDE is a shuffle of twins because it can be formed by shuffling ABCDE and ABCDE. DBEACBCADE is not a shuffle of twins because it cannot be formed by shuffling two identical strings.

Program Details

Given an input string, output 0 if it is not a shuffle of twins, and output one of the twin strings if it is a shuffle of twins.

You may assume that the input string has a length inclusively between four and twenty characters and is composed entirely of uppercase alphabetic characters. It should be able to run in a reasonable amount of time, say, under 10 minutes.

This is code golf, so the shortest solution wins.

Example I/O

&gt; ABACBDECDE
ABCDE

&gt; DBEACBCADE
0

&gt; FFFFFF
FFF

&gt; FFGGG
0

&gt; ABBA
0

&gt; AABB
AB

&gt; AABAAB
AAB


I have an example (non-golfed) implementation.
Haskell, 114

main=getLine&gt;&gt;=putStrLn.f.p;f x=head$[a|(a,b)&lt;-x,a==b]++["0"]
p[]=[([],[])];p(x:y)=do(a,b)&lt;-p y;[(x:a,b),(a,x:b)]


Ungolfed:

main :: IO ()
main = getLine &gt;&gt;= putStrLn . findMatch . partitions

-- | Find the first partition where the two subsequences are
-- equal. If none are, return "0".
findMatch :: [(String, String)] -&gt; String
findMatch ps = head $ [a | (a,b) &lt;- ps, a == b] ++ ["0"]

-- | Return all possible partitions of the input into two
-- subsequences. Preserves the order of each subsequence.
--
-- Example:
-- partitions "AB" == [("AB",""),("B","A"),("A","B"),("","AB")]
partitions :: [a] -&gt; [([a], [a])]
partitions []     = [([], [])]
partitions (x:xs) = do (a, b) &lt;- partitions xs
                       [(x:a, b), (a, x:b)]


Explanation:

Most of the work is being done in the partitions function. It works by
recursively generating all partitions (a, b) of the tail of the list,
and then using the list monad to prepend the initial element x to each of
them and gather all the results.

findMatch works by filtering this list so that only partitions where the
subsequences are equal remain. It then returns the first subsequence in the first
partition. If none remain, the list is empty, so the "0" appended at the
end gets returned instead.

main just reads the input, feeds it through these two functions and prints it.