Task
Define a simple regex as a non-empty regular expression consisting only of
- characters
0
and1
, - grouping parentheses
(
and)
, - one-or-more repetition quantifier
+
.
Given a non-empty string of 0
s and 1
s, your program should find the shortest simple regex matching the full input string. (That is, when matching a simple regex, pretend it’s bookended by ^
and $
.) If there are multiple shortest regexes, print any or all of them.)
code-golf, so the shortest submission (in bytes) wins.
Test cases
1 -> 1
00 -> 00 or 0+
010 -> 010
1110 -> 1+0
01010 -> 01010
0101010 -> 0(10)+ or (01)+0
011111 -> 01+
10110110 -> (1+0)+
01100110 -> (0110)+ or (01+0)+
010010010 -> (010)+
111100111 -> 1+001+ or 1+0+1+
00000101010 -> 0+(10)+ or (0+1)+0
1010110001 -> 1(0+1+)+ or (1+0+)+1
01100110
is an interesting case... a naïve algorithm would write01+0+1+0
or(0+1+)+0
which aren't optimal. \$\endgroup\$