Select Code to Download

Regular Expressions
Time limit     10 seconds
...
For instance, the regular expression (a*) matches any string containin
+g only letters a, including an empty string. The regular expression (
+0*) only matches an empty string (which can be split into zero parts 
+matching the expression 0). The regular expression (a|(g(tc))) matche
+s two strings: a and gtc. Note that it is forbidden to omit or add ex
+tra brackets to regular expressions: it must contain strictly those p
+airs of brackets which appear during its construction according to th
+e rules described above.

Simon wants a flawless victory by building the shortest matching regul
+ar expression. Help Simon. Write a program which finds the shortest r
+egular expression for a set of strings, such that all these strings m
+atch the expression.

The first line contains an integer T — the number of tests. It is foll
+owed by test descriptions.

The first line of a test description contains a single positive intege
+r N — the number of strings in the set. Each of the following N lines
+ begins with a nonnegative integer L — the length of the string from 
+the set, followed by the string itself, separated by a space. The str
+ing only contains lowercase latin letters a, g, t, c. Note that a str
+ing in the set can be empty. In this case the line in the file will o
+nly contain the digit 0 and a space symbol.

The total number of strings in all sets is not greater than 2000. The 
+sum of lengths of all strings in all sets is not greater than 2000.

Print precisely T regular expressions, one per line. Each regular expr
+ession must be an answer to a corresponding test. If for any test the
+re is no regular expression matched by all strings from the set, prin
+t the word Impossible instead of the answer.

3
2
...
1 g
2 gg
3 ggg

(a|(g(tc)))
(0*)
(g*)

The sixth line of the input data in the example zero is followed by a 
+space symbol.

#!/usr/bin/perl

...
    
    return @combs;
    }

*
2
...
- aaaacgcgaaaattttttcgcg
1
- acg

(a|((gt)c))
(c*)
...
real    0m0.616s
user    0m0.584s
sys    0m0.028s

4
16
...
real    0m0.678s
user    0m0.668s
sys    0m0.004s