132 lines
3.3 KiB
Text
132 lines
3.3 KiB
Text
use Collection.Generic;
|
|
|
|
class Eertree {
|
|
function : Main(args : String[]) ~ Nil {
|
|
tree := GetEertree("eertree");
|
|
Show(SubPalindromes(tree));
|
|
}
|
|
|
|
function : GetEertree(s : String) ~ Vector<Node> {
|
|
tree := Vector->New()<Node>;
|
|
tree->AddBack(Node->New(0, Nil, 1));
|
|
tree->AddBack(Node->New(-1, Nil, 1));
|
|
suffix := 1;
|
|
|
|
n : Int; k : Int;
|
|
for(i := 0; i < s->Size(); ++i;) {
|
|
c := s->Get(i);
|
|
|
|
done := false;
|
|
for (j := suffix; <>done; j := tree->Get(j)->GetSuffix();) {
|
|
k := tree->Get(j)->GetLength();
|
|
b := i - k - 1;
|
|
if (b >= 0 & s->Get(b) = c) {
|
|
n := j;
|
|
done := true;
|
|
};
|
|
};
|
|
skip := false;
|
|
if (tree->Get(n)->GetEdges()->Has(c)) {
|
|
suffix := tree->Get(n)->GetEdges()->Find(c)->Get();
|
|
skip := true;
|
|
};
|
|
|
|
if(<>skip) {
|
|
suffix := tree->Size();
|
|
tree->AddBack(Node->New(k + 2));
|
|
tree->Get(n)->GetEdges()->Insert(c, suffix);
|
|
if (tree->Get(suffix)->GetLength() = 1) {
|
|
tree->Get(suffix)->SetSuffix(0);
|
|
skip := true;
|
|
};
|
|
|
|
if(<>skip) {
|
|
done := false;
|
|
while (<>done) {
|
|
n := tree->Get(n)->GetSuffix();
|
|
b := i - tree->Get(n)->GetLength() - 1;
|
|
if (b >= 0 & s->Get(b) = c) {
|
|
done := true;
|
|
};
|
|
};
|
|
tree->Get(suffix)->SetSuffix(tree->Get(n)->GetEdges()->Find(c)->Get());
|
|
};
|
|
};
|
|
};
|
|
|
|
return tree;
|
|
}
|
|
|
|
function : SubPalindromes(tree : Vector<Node>) ~ Vector<String> {
|
|
s := Vector->New()<String>;
|
|
SubPalindromesChildren(0, "", tree, s);
|
|
|
|
keys := tree->Get(1)->GetEdges()->GetKeys()<CharHolder>;
|
|
each(k : keys) {
|
|
key := keys->Get(k);
|
|
str := key->Get()->ToString();
|
|
s->AddBack(str);
|
|
value := tree->Get(1)->GetEdges()->Find(key)->As(IntHolder)->Get();
|
|
SubPalindromesChildren(value, str, tree, s);
|
|
};
|
|
|
|
return s;
|
|
}
|
|
|
|
function : SubPalindromesChildren(n : Int, p : String, tree : Vector<Node>, s : Vector<String>) ~ Nil {
|
|
keys := tree->Get(n)->GetEdges()->GetKeys()<CharHolder>;
|
|
each(k : keys) {
|
|
key := keys->Get(k);
|
|
c := key->Get();
|
|
value := tree->Get(n)->GetEdges()->Find(key)->As(IntHolder)->Get();
|
|
str := ""; str += c; str += p; str += c;
|
|
s->AddBack(str);
|
|
SubPalindromesChildren(value, str, tree, s);
|
|
};
|
|
}
|
|
|
|
function : Show(result : Vector<String>) ~ Nil {
|
|
out := "[";
|
|
each(i : result) {
|
|
out += result->Get(i);
|
|
if(i + 1 < result->Size()) {
|
|
out += ", ";
|
|
};
|
|
};
|
|
out += "]";
|
|
out->PrintLine();
|
|
}
|
|
}
|
|
|
|
class Node {
|
|
@length : Int;
|
|
@edges : Map<CharHolder, IntHolder>;
|
|
@suffix : Int;
|
|
|
|
New(length : Int, edges : Map<CharHolder, IntHolder>, suffix : Int) {
|
|
@length := length;
|
|
@edges := edges <> Nil ? edges : Map->New()<CharHolder, IntHolder>;
|
|
@suffix := suffix;
|
|
}
|
|
|
|
New(length : Int) {
|
|
@length := length;
|
|
@edges := Map->New()<CharHolder, IntHolder>;
|
|
}
|
|
|
|
method : public : GetLength() ~ Int {
|
|
return @length;
|
|
}
|
|
|
|
method : public : GetSuffix() ~ Int {
|
|
return @suffix;
|
|
}
|
|
|
|
method : public : SetSuffix(suffix : Int) ~ Nil {
|
|
@suffix := suffix;
|
|
}
|
|
|
|
method : public : GetEdges() ~ Map<CharHolder, IntHolder> {
|
|
return @edges;
|
|
}
|
|
}
|