1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl
#
# a-palindrome-grows-in-brooklyn.pl
#
# I think the result here, of a new tool to find out all things
# palindromic, is not really the most practical thing. However the
# algorithm used to get there is quite interesting and novel.
#
# I say the algorithm is novel, and I mean it: its only a few years
# old and represents a new data structure that solves the problem
# with a remarkably efficient computational complxity.
#
# Consider it as two interwoven trees, one containing palidromic
# segments and the other
# ref:
# https://www.geeksforgeeks.org/palindromic-tree-introduction-implementation/
#
# © 2021 colin crain
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
package PNode;
use Moo;
has start => ( is => 'rw' );
has end => ( is => 'rw' );
has length => ( is => 'rw' );
has insert_link => ( is => 'rw',
default => sub {
return { map { $_, 0 } ('a'..'z') } } );
has suffix_link => ( is => 'rw' );
### ### ### main body
use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
package main;
my $input = shift // 'amanaplanacanalpanama'; ## <-- input here
my @s = split //, $input;
my $root1 = PNode->new( length => -1, suffix_link => 1 );
my $root2 = PNode->new( length => 0, suffix_link => 1 );
our @tree = ( undef, $root1, $root2 );
our $curr_node = 1;
our $node_ptr = 2;
## traverse the string and insert each character into the structure
insert( $_ ) for keys @s;
## output
say "all distinct palindromic substrings for ", @s, " : \n";
for my $i (3..$node_ptr) {
print $i-2, ") ";
say substr $input, $tree[$i]->start, $tree[$i]->length;
}
sub insert( $idx ) {
## FIND MAX PALINDROME AT $idx
## search for a node containing a substring such that the character at
## the current index plus the substring defined by the located node,
## plus the character again, is the maximum palindrome at idx:
## $s[$idx].X.$s[$idx] We iterate down the suffix link chain from
## $curr_node to find X
my $tmp = $curr_node;
while (1) {
my $curr_length = $tree[$tmp]->length;
last if ($idx - $curr_length >= 1 and $s[$idx] eq $s[$idx - $curr_length - 1]) ;
$tmp = $tree[$tmp]->suffix_link;
}
## check to see whether palindrome string $s[$idx].X.$s[$idx]
## already exists or not
if( $tree[$tmp]->insert_link->{ $s[$idx] } != 0 ) {
## substring already exists in the tree
$curr_node = $tree[$tmp]->insert_link->{ $s[$idx] };
return;
}
## ADD NEW NODE AS CHILD OF X:
## parent link to new node position, weight as $s[$idx]
$tree[$tmp]->insert_link->{ $s[$idx] } = ++$node_ptr ;
## create new node: start, end, length of substring
$tree[$node_ptr] = PNode->new(
length => $tree[$tmp]->length + 2 ,
end => $idx ,
start => $idx - ($tree[$tmp]->length + 2) + 1 ,
);
## SET SUFFIX EDGE FOR NEW NODE
## Find some string Y such that
## $s[$idx].Y.$s[$idx] is longest possible
## palindromic suffix for newly created Node.
$tmp = $tree[$tmp]->suffix_link;
## making new Node as current Node
$curr_node = $node_ptr;
if ($tree[$curr_node]->length == 1) {
## if new palindrome's lengthgth is 1
## making its suffix link to be null string
$tree[$curr_node]->suffix_link( 2 );
return;
}
while (1) {
my $curr_lengthgth = $tree[$tmp]->length;
last if ($idx - $curr_lengthgth >= 1 and $s[$idx] eq $s[$idx-$curr_lengthgth-1]) ;
$tmp = $tree[$tmp]->suffix_link;
}
## linking current PNode suffix_link with $s[$idx].Y.$s[$idx]
$tree[$curr_node]->suffix_link( $tree[$tmp]->insert_link->{ $s[$idx] } );
}
|
