73 lines
1.5 KiB
D
73 lines
1.5 KiB
D
import std.array;
|
|
import std.stdio;
|
|
|
|
void main() {
|
|
auto tree = eertree("eertree");
|
|
writeln(subPalindromes(tree));
|
|
}
|
|
|
|
struct Node {
|
|
int length;
|
|
int[char] edges;
|
|
int suffix;
|
|
}
|
|
|
|
const evenRoot = 0;
|
|
const oddRoot = 1;
|
|
|
|
Node[] eertree(string s) {
|
|
Node[] tree = [
|
|
Node(0, null, oddRoot),
|
|
Node(-1, null, oddRoot),
|
|
];
|
|
int suffix = oddRoot;
|
|
int n, k;
|
|
foreach (i, c; s) {
|
|
for (n=suffix; ; n=tree[n].suffix) {
|
|
k = tree[n].length;
|
|
int b = i-k-1;
|
|
if (b>=0 && s[b]==c) {
|
|
break;
|
|
}
|
|
}
|
|
if (c in tree[n].edges) {
|
|
suffix = tree[n].edges[c];
|
|
continue;
|
|
}
|
|
suffix = tree.length;
|
|
tree ~= Node(k+2);
|
|
tree[n].edges[c] = suffix;
|
|
if (tree[suffix].length == 1) {
|
|
tree[suffix].suffix = 0;
|
|
continue;
|
|
}
|
|
while (true) {
|
|
n = tree[n].suffix;
|
|
int b = i-tree[n].length-1;
|
|
if (b>=0 && s[b]==c) {
|
|
break;
|
|
}
|
|
}
|
|
tree[suffix].suffix = tree[n].edges[c];
|
|
}
|
|
return tree;
|
|
}
|
|
|
|
auto subPalindromes(Node[] tree) {
|
|
auto s = appender!(string[]);
|
|
void children(int n, string p) {
|
|
foreach (c, n; tree[n].edges) {
|
|
p = c ~ p ~ c;
|
|
s ~= p;
|
|
children(n, p);
|
|
}
|
|
}
|
|
children(0, "");
|
|
foreach (c, n; tree[1].edges) {
|
|
string ct = [c].idup;
|
|
s ~= ct;
|
|
children(n, ct);
|
|
}
|
|
return s.data;
|
|
}
|