Eertree: Difference between revisions
→{{header|Perl}}
SqrtNegInf (talk | contribs) (Added Perl example) |
|||
Line 796:
<pre>
("ee", "e", "r", "t", "rtr", "ertre", "eertree")
</pre>
=={{header|Obeck}}==
{{trans|Java}}
<lang objeck>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;
}
}</lang>
{{output}}
<pre>
[ee, e, r, t, rtr, ertre, eertree]
</pre>
| |||