summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJesse Luehrs <doy@tozt.net>2012-11-17 15:20:08 -0600
committerJesse Luehrs <doy@tozt.net>2012-11-17 15:20:08 -0600
commitde60194c4c0e7a8b509c42f4b09f9795e30a5c7f (patch)
tree8ded45258ae68baa8f73cf8ac98f977ac650be14
parentc6e3fc727f612c63f1f970a110195ee3642e49d5 (diff)
downloadrosalind-de60194c4c0e7a8b509c42f4b09f9795e30a5c7f.tar.gz
rosalind-de60194c4c0e7a8b509c42f4b09f9795e30a5c7f.zip
another solution
-rw-r--r--SUFF.pl83
1 files changed, 83 insertions, 0 deletions
diff --git a/SUFF.pl b/SUFF.pl
new file mode 100644
index 0000000..f82bbfc
--- /dev/null
+++ b/SUFF.pl
@@ -0,0 +1,83 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use 5.016;
+
+use constant DEBUG => 0;
+
+chomp(my $str = <>);
+my @suffixes = map { substr($str, $_ - 1) } 1..length($str);
+
+my %nodes = (
+ node1 => {
+ str => '',
+ children => [],
+ },
+);
+
+my $i = 1;
+my $step = 1;
+SUFFIX: for my $suffix (@suffixes) {
+ insert($suffix, 'node1');
+ render_as_dot(\%nodes, $step++) if DEBUG;
+}
+
+delete $nodes{node1};
+say for map { $_->{str} } values %nodes;
+
+sub insert {
+ my ($str, $root) = @_;
+
+ return unless length($str);
+
+ for my $child (@{ $nodes{$root}{children} }) {
+ my $child_str = $nodes{$child}{str};
+ my @prefixes = reverse map { substr($child_str, 0, $_) }
+ 1..length($child_str);
+ for my $prefix (@prefixes) {
+ if ($str =~ s/^\Q$prefix//) {
+ $child_str =~ s/^\Q$prefix//;
+
+ $nodes{$child}{str} = $prefix;
+
+ if (@{ $nodes{$child}{children} } && length($child_str)) {
+ my $new_node = 'node' . ++$i;
+ $nodes{$new_node} = {
+ str => $child_str,
+ children => $nodes{$child}{children},
+ parent => $child,
+ };
+ $nodes{$child}{children} = [$new_node];
+ $nodes{$_}{parent} = $new_node
+ for @{ $nodes{$new_node}{children} };
+ }
+ else {
+ insert($child_str, $child);
+ }
+
+ insert($str, $child);
+
+ return;
+ }
+ }
+ }
+
+ my $new_node = 'node' . ++$i;
+ push @{ $nodes{$root}{children} }, $new_node;
+ $nodes{$new_node} = {
+ str => $str,
+ children => [],
+ parent => $root,
+ };
+}
+
+sub render_as_dot {
+ my ($graph, $step) = @_;
+ open my $fh, '>', "step$step.dot" or die "Couldn't open step$step.dot: $!";
+ say $fh "graph step$step {";
+ for my $node (keys %$graph) {
+ next unless $nodes{$node}{parent};
+ say $fh " $nodes{$node}{parent} -- $node [label=\"$nodes{$node}{str}\"];";
+ }
+ say $fh "}";
+}