fork download
  1. #!/usr/bin/perl
  2.  
  3. use warnings;
  4. use strict;
  5. use re 'eval';
  6.  
  7. use Time::HiRes qw( gettimeofday tv_interval );
  8.  
  9. my $t0 = [ gettimeofday ];
  10.  
  11. $\ = $/;
  12. my $debug = 1;
  13. my $debug2 = 0;
  14. my $time = 0;
  15.  
  16. my @acgt = qw( a c g t );
  17.  
  18. my @combinations = map { [ combinations( $_, $_ - 1, @acgt ) ] } 1 .. 5;
  19.  
  20. $debug and print ~~ @{ $_ } for @combinations;
  21.  
  22. my %regexes = ( '_' => 1 );
  23.  
  24. while( 1 ){
  25. my @old_regexes = sort { length $a <=> length $b || $a cmp $b } keys %regexes;
  26. $debug and print " " . @old_regexes;
  27.  
  28. for my $i ( 0 .. @old_regexes - 1 ){
  29. my $copy_of_index_i = $i;
  30. $i = $old_regexes[ $i ];
  31.  
  32. if( $i !~ /\*/ ){
  33. $regexes{ "($i*)" } ++ if ( length $i ) + 3 < 16;
  34.  
  35. for my $j ( $copy_of_index_i + 0 .. @old_regexes - 1 ){
  36. $j = $old_regexes[ $j ];
  37. last if ( length $i ) + ( length $j ) + 3 > 15;
  38. next if $j =~ /\*/;
  39. $regexes{ "($i|$j)" } ++;
  40. # $regexes{ "($j|$i)" } ++;
  41. }
  42. }
  43.  
  44. for my $j ( $copy_of_index_i + 0 .. @old_regexes - 1 ){
  45. $j = $old_regexes[ $j ];
  46. last if ( length $i ) + ( length $j ) + 2 > 15;
  47. next if $i =~ /\*/ && $j =~ /\*/;
  48. $regexes{ "($i$j)" } ++;
  49. $regexes{ "($j$i)" } ++;
  50. }
  51. }
  52.  
  53. last if @old_regexes == keys %regexes;
  54. }
  55.  
  56. $debug2 and print "regexes(30): ", join ' ', ( sort { length $a <=> length $b } keys %regexes )[ 0 .. 30 ];
  57.  
  58. $debug and print "number of abstract regexes: " . keys %regexes;
  59.  
  60. my %uniq;
  61. map $uniq{ $_ } ++, keys %regexes;
  62. %regexes = map { $_ => 1 } keys %uniq;
  63.  
  64. $debug and print ~~ keys %regexes;
  65.  
  66. for my $re ( sort keys %regexes ){
  67. $re =~ / (\w) [(] (\w)(\w) [)] /x or next;
  68. delete $regexes{ $re };
  69. $re =~ s/ (\w) [(] (\w)(\w) [)] /($1$2)$3/x;
  70. $regexes{ $re } ++;
  71. }
  72.  
  73. $debug and print ~~ keys %regexes;
  74.  
  75. for my $re ( sort keys %regexes ){
  76. $re =~ / (\w) [(] [(] (\w)(\w) [)] (\w) [)] /x or next;
  77. delete $regexes{ $re };
  78. $re =~ s/ (\w) [(] [(] (\w)(\w) [)] (\w) [)] /(($1$2)$3)$4/x;
  79. $regexes{ $re } ++;
  80. }
  81.  
  82. $debug and print ~~ keys %regexes;
  83.  
  84. for my $re ( sort keys %regexes ){
  85. $re =~ / [(] (\w) (\w) [)] [(] (\w) (\w) [)] /x or next;
  86. delete $regexes{ $re };
  87. $re =~ s/ [(] (\w) (\w) [)] [(] (\w) (\w) [)] /(($1$2)$3)$4/x;
  88. $regexes{ $re } ++;
  89. }
  90.  
  91. $debug and print ~~ keys %regexes;
  92.  
  93. $regexes{ "((((a|c)|g)|t)*)" } ++;
  94.  
  95. $debug and print ~~ keys %regexes;
  96.  
  97. my @regexes = sort { length $a <=> length $b } keys %regexes;
  98.  
  99. y/_/./ for @regexes;
  100.  
  101. $debug2 and print "regexes(30): @regexes[ 0 .. 30 ]";
  102.  
  103. %regexes = map { $_ => 1 } @regexes;
  104.  
  105. my %HoR;
  106.  
  107. for my $re ( keys %regexes ){
  108. my $cnt = () = $re =~ /\./g;
  109.  
  110. for my $comb ( @{ $combinations[ $cnt - 1 ] } ){
  111. $_ = $re;
  112. for my $letter ( split //, $comb ){
  113. s/\./$letter/;
  114. }
  115. next if /\*/ and 4 == $cnt and /(\w).*\1/;
  116. next if / [(] (\w) \| (\w) [)] /x and $1 ge $2;
  117. next if / [(] [(] (\w) \| (\w) [)] \| (\w) [)] /x and $1 ge $2 || $1 ge $3 || $2 ge $3;
  118. push @{ $HoR{ $re } }, qr/^$_$/;
  119. }
  120. }
  121.  
  122. if( $debug ){
  123. my @c = ( 0 ) x 5;
  124. my $c = 0;
  125. for my $re ( keys %HoR ){
  126. my $cnt = () = $re =~ /\./g;
  127. $c[ $cnt - 1 ] += @{ $HoR{ $re } };
  128. $c += @{ $HoR{ $re } };
  129. }
  130. print "all regexes: " . $c;
  131. print " $_" for @c;
  132. }
  133.  
  134. $time and print ' ', tv_interval( $t0 );
  135.  
  136. ################ MAIN:
  137.  
  138. <>;
  139.  
  140. while( <> ){
  141. @_ = map ~~<>, 1 .. $_;
  142. chomp @_;
  143. s/\S+ // for @_;
  144. $debug2 and print "\@_:@_";
  145.  
  146. s/(.)\1{2,}/ $1 x 3 /ge for @_;
  147. s/(.{2,4})\1{2,}/ $1 x 2 /ge for @_;
  148.  
  149. $time and print ' ', tv_interval( $t0 );
  150.  
  151. my %uniq;
  152. map $uniq{ $_ } ++, @_;
  153. @_ = sort keys %uniq;
  154.  
  155. my @regexes = sort { length $a <=> length $b } keys %HoR;
  156.  
  157. for my $str ( @_ ){
  158. $debug and print " candidate abstract regexes: " . @regexes;
  159. $debug2 and print " str:[$str]";
  160. my @ok;
  161.  
  162. for my $re ( @regexes ){
  163. $str =~ /^$re$/ and push @ok, $re;
  164. }
  165.  
  166. @regexes = @ok;
  167. }
  168.  
  169. $debug and print " abstract regexes which match: " . @regexes;
  170. $debug2 and print " abstract regexes: @regexes";
  171.  
  172. my @real;
  173.  
  174. @regexes = map @{ $HoR{ $_ } }, @regexes;
  175.  
  176. for my $str ( @_ ){
  177. $debug and print " candidate regexes: " . @regexes;
  178. $debug2 and print " str:[$str]";
  179. my @ok;
  180.  
  181. for my $re ( @regexes ){
  182. $str =~ $re and push @ok, $re; # HOT SPOT
  183. }
  184.  
  185. @regexes = @ok;
  186. }
  187.  
  188. $debug and print " regexes which match: " . @regexes;
  189.  
  190. my $shortest = shift @regexes;
  191.  
  192. my $strip = join "(.*)", map quotemeta, qw[ (?^:^ $) ];
  193. map { s/^ $strip $/$1/x } $shortest;
  194.  
  195. #^ map { s/^ \Q(?^:^\E //x, s/ \Q$)\E $//x } $shortest; # alternative: OK
  196.  
  197. print $shortest ? $shortest : "Impossible";
  198.  
  199. $time and print tv_interval( $t0 );
  200.  
  201. $debug and print '-' x 20;
  202. }
  203.  
  204. ########## END MAIN
  205.  
  206. sub combinations {
  207. my( $length, $min_set, @letters ) = @_;
  208.  
  209. my $str = join '-', ( join '', @letters ) x $length;
  210. $debug2 and print $str;
  211.  
  212. my $re = join join( '-', ( '.*?' ) x 2 ), ('(.)') x $length;
  213. $debug2 and print $re;
  214.  
  215. my %combs;
  216.  
  217. $str =~ /$re (?{ $combs{ join '', grep defined, $1, $2, $3, $4, $5 } ++ }) (*FAIL)/x;
  218.  
  219. my @combs = keys %combs;
  220.  
  221. $debug2 and print "all combs: " . @combs;
  222.  
  223. # @combs = grep { !/(.)\1/ } @combs;
  224. # $debug2 and print "all combs: " . @combs;
  225.  
  226. @combs = grep {
  227. my %uniq;
  228. map $uniq{ $_ } ++, split //;
  229. $min_set <= keys %uniq;
  230. } @combs;
  231.  
  232. $debug2 and print "unique combs: " . @combs;
  233. $debug2 and print "@combs";
  234.  
  235. return @combs;
  236. }
Success #stdin #stdout 0.53s 36444KB
stdin
*
2
1 a
3 gtc
1
0 
3
1 g
2 gg
3 ggg
2
- tcac
- gcac
2
- tac
- gtc
2
- gag
- tcag
2
- ga
- ctca
2
- a
- acaca
2
- aaa
- cccc
3
- aaa
- ccc
- ttt
4
- a
- c
- g
- t
4
- aaaaa
- c
- g
- t
3
- acac
- caca
- g
1
- g
1
- gcgc
1
- gcgcg
1
- acacacacacacacacacac
1
- aaaaaaaaaaaaaaaaaaaaaaaaaac
1
- aaaaaaaaaacg
1
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
1
- acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac
1
- acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacg
1
- acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacgt
9
- a
- aaaaaaaaaaaaaaaaaaaaaaa
- aa
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacccc
- aac
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
- ac
- aaaaaac
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
32
- a
- c
- t
- g
- aa
- cc
- tt
- gg
- a
- c
- t
- g
- aa
- cc
- tt
- gg
- a
- c
- t
- g
- aa
- cc
- tt
- gg
- a
- c
- t
- g
- aa
- cc
- tt
- gg
2
- acgtgca
- 
2
- acgt
- 
1
- aaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccctaaaaaaaaaaaaacccccccccccccct
1
- acggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgaacggcagcgagcgacgacgacgacgagcgacggacggacggacggagcggacggacggacgacgacgagcgacggagcgagcgacggacgagcgacgat
1
- acgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacg
1
- acgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgt
2
- 
- 
2
- 
- c
3
- 
- c
- t
3
- 
- ccc
- t
2
- acgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgt
- acgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacgacga
2
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacgcgcgcgcgcgcgcgaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacgcgcgcgcgcgcgcgaaaaaaaaaaaaaaaaaaaaaaaaaaaaaat
8
- aaaacgcgaaaa
- aaaacgcgaaaat
- aaaacgcgaaaatttttt
- aaaacgcgaaaatttt
- aaaacgcgcgaaaatttttt
- aaaaaaacgcgaaaatttttt
- cgcgaaaatttttt
- aaaacgcgaaaattttttcgcg
1
- acg
stdout
4
16
60
168
240
    1
    4
    25
    144
    235
number of abstract regexes: 235
235
208
203
198
199
all regexes: 15264
 8
 76
 960
 3384
 10836
 candidate abstract regexes: 199
 candidate abstract regexes: 60
 abstract regexes which match: 45
 candidate regexes: 2550
 candidate regexes: 954
 regexes which match: 292
(a|((gt)c))
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 27
 candidate regexes: 746
 regexes which match: 746
(t*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 60
 candidate abstract regexes: 35
 abstract regexes which match: 28
 candidate regexes: 1194
 candidate regexes: 528
 candidate regexes: 318
 regexes which match: 318
(g*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 114
 abstract regexes which match: 114
 candidate regexes: 6382
 candidate regexes: 284
 regexes which match: 249
((((g|t)c)a)c)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 136
 abstract regexes which match: 136
 candidate regexes: 9366
 candidate regexes: 669
 regexes which match: 249
(((gt)|(ta))c)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 136
 abstract regexes which match: 76
 candidate regexes: 3210
 candidate regexes: 277
 regexes which match: 245
((g|(tc))(ag))
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 114
 abstract regexes which match: 67
 candidate regexes: 2086
 candidate regexes: 258
 regexes which match: 246
((g|((ct)c))a)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 60
 abstract regexes which match: 34
 candidate regexes: 906
 candidate regexes: 462
 regexes which match: 261
((a|c)*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 136
 abstract regexes which match: 136
 candidate regexes: 9366
 candidate regexes: 318
 regexes which match: 255
((a|c)*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 136
 candidate abstract regexes: 136
 abstract regexes which match: 136
 candidate regexes: 9366
 candidate regexes: 318
 candidate regexes: 255
 regexes which match: 243
((a|(c|t))*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 60
 candidate abstract regexes: 60
 candidate abstract regexes: 60
 abstract regexes which match: 60
 candidate regexes: 3940
 candidate regexes: 1444
 candidate regexes: 466
 candidate regexes: 306
 regexes which match: 264
((a|t)|(c|g))
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 136
 candidate abstract regexes: 45
 candidate abstract regexes: 45
 abstract regexes which match: 45
 candidate regexes: 2550
 candidate regexes: 318
 candidate regexes: 257
 candidate regexes: 243
 regexes which match: 240
((((a|c)|g)|t)*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 114
 candidate abstract regexes: 114
 abstract regexes which match: 29
 candidate regexes: 1002
 candidate regexes: 268
 candidate regexes: 255
 regexes which match: 243
((a|(c|g))*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 60
 candidate regexes: 3940
 regexes which match: 1444
g
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 114
 candidate regexes: 6382
 regexes which match: 293
((gc)*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 82
 candidate regexes: 2922
 regexes which match: 261
((c|g)*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 84
 candidate regexes: 2062
 regexes which match: 293
((ac)*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 114
 candidate regexes: 6382
 regexes which match: 283
((a*)c)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 82
 candidate regexes: 2922
 regexes which match: 264
(((a*)c)g)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 114
 candidate regexes: 6382
 regexes which match: 283
((a*)c)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 85
 candidate regexes: 2086
 regexes which match: 293
((ac)*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 78
 candidate regexes: 1962
 regexes which match: 260
(((ac)*)g)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 91
 candidate regexes: 2194
 regexes which match: 258
(((ac)*)(gt))
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 60
 candidate abstract regexes: 35
 candidate abstract regexes: 28
 candidate abstract regexes: 26
 candidate abstract regexes: 26
 candidate abstract regexes: 26
 abstract regexes which match: 26
 candidate regexes: 714
 candidate regexes: 408
 candidate regexes: 318
 candidate regexes: 318
 candidate regexes: 258
 candidate regexes: 256
 candidate regexes: 256
 regexes which match: 256
((a|c)*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 60
 candidate abstract regexes: 35
 candidate abstract regexes: 35
 candidate abstract regexes: 35
 candidate abstract regexes: 35
 candidate abstract regexes: 35
 candidate abstract regexes: 35
 abstract regexes which match: 35
 candidate regexes: 2118
 candidate regexes: 813
 candidate regexes: 318
 candidate regexes: 257
 candidate regexes: 255
 candidate regexes: 243
 candidate regexes: 243
 candidate regexes: 240
 regexes which match: 240
((((a|c)|g)|t)*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 27
 abstract regexes which match: 12
 candidate regexes: 466
 candidate regexes: 466
 regexes which match: 240
((((a|c)|g)|t)*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 27
 abstract regexes which match: 20
 candidate regexes: 614
 candidate regexes: 614
 regexes which match: 256
((((ac)g)t)*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 86
 candidate regexes: 2110
 regexes which match: 243
((a|(c|t))*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 80
 candidate regexes: 2010
 regexes which match: 243
(((g|(a|c))*)t)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 90
 candidate regexes: 2170
 regexes which match: 265
(((ac)g)*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 80
 candidate regexes: 2010
 regexes which match: 253
((((ac)g)*)t)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 27
 candidate regexes: 746
 regexes which match: 746
(t*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 27
 abstract regexes which match: 10
 candidate regexes: 418
 candidate regexes: 418
 regexes which match: 304
(c*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 27
 candidate abstract regexes: 10
 abstract regexes which match: 10
 candidate regexes: 418
 candidate regexes: 418
 candidate regexes: 304
 regexes which match: 255
((c|t)*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 27
 candidate abstract regexes: 19
 abstract regexes which match: 10
 candidate regexes: 418
 candidate regexes: 418
 candidate regexes: 304
 regexes which match: 255
((c|t)*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 80
 abstract regexes which match: 80
 candidate regexes: 2010
 candidate regexes: 249
 regexes which match: 243
((a|(t|(cg)))*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 83
 abstract regexes which match: 70
 candidate regexes: 1770
 candidate regexes: 249
 regexes which match: 243
((a|(t|(cg)))*)
--------------------
 candidate abstract regexes: 199
 candidate abstract regexes: 85
 candidate abstract regexes: 70
 candidate abstract regexes: 70
 candidate abstract regexes: 70
 abstract regexes which match: 70
 candidate regexes: 1770
 candidate regexes: 249
 candidate regexes: 243
 candidate regexes: 243
 candidate regexes: 243
 regexes which match: 243
((a|(t|(cg)))*)
--------------------
 candidate abstract regexes: 199
 abstract regexes which match: 136
 candidate regexes: 9366
 regexes which match: 669
((ac)g)
--------------------