خب یکم قلق داره و از این ویدیو استفاده کردم: https://www.youtube.com/watch?v=VA9m_l6LpwI
طبق این ویدیو کد زیر رو نوشتم که با دو تست banana و CAGTCAGG (مثال ویدیو) خروجی زیر رو میده:
----------- Test1 -----------[P:null,L0]: (-1,null)
[P:root,L1]: (-1,a)
[P:a,L2]: (5,$)
[P:a,L2]: (-1,na)
[P:na,L3]: (3,$)
[P:na,L3]: (1,na$)
[P:root,L1]: (-1,na)
[P:na,L2]: (4,$)
[P:na,L2]: (2,na$)
[P:root,L1]: (0,banana$)
----------- Test2 -----------
[P:null,L0]: (-1,null)
[P:root,L1]: (-1,G)
[P:G,L2]: (7,$)
[P:G,L2]: (6,G$)
[P:G,L2]: (2,TCAGG$)
[P:root,L1]: (-1,AG)
[P:AG,L2]: (5,G$)
[P:AG,L2]: (1,TCAGG$)
[P:root,L1]: (-1,CAG)
[P:CAG,L2]: (4,G$)
[P:CAG,L2]: (0,TCAGG$)
[P:root,L1]: (3,TCAGG$)
که ایندکس ها برخلاف ویدیو از صفر شروع میشه. L هم سطح گره در درخت رو مشخص میکنه و ایندکس -1 هم به معنی نودهای میانی است. (ویرایش/حل شد:با این وجود مثال دوم "L[2]: (-1,)" اشتباهه و بقیش درست به نظر میاد که احتمالا جایی باگ داره و دقت نکردم، همینشم وقت گیر بود یکم.)
مشکل هم به این صورت حل شد که if (this.index == -1) { //non-leaf (including root at start) که قبلا if(this.value==null بود و فقط root رو در نظر میگرفت ولی این حالت برای نودهای میانی که قبلا شاخه شاخه شدن هم وجود داره و باید در نظر گرفت
کد:
package main;
import java.util.ArrayList;
import javafx.util.Pair;
public class SuffixTree {
public static void main(String[] args) {
System.out.println("----------- Test1 -----------");
SuffixTree suffixTree = new SuffixTree("banana");
printNode(null, suffixTree.root, 0);
System.out.println("----------- Test2 -----------");
SuffixTree suffixTree2 = new SuffixTree("CAGTCAGG");
printNode(null, suffixTree2.root, 0);
}
public static void printNode(Node parent, Node node, int depth) {
if (parent != null) {
System.out.println("[P:" + (parent.value==null?"root":parent.value) + ",L:" + depth + "]: (" + node.index + "," + node.value + ")");
} else {
System.out.println("[P:null,L:" + depth + "]: (" + node.index + "," + node.value + ")");
}
for (Node n : node.children) {
printNode(node, n, depth + 1);
}
}
Node root;
String mainString;
ArrayList<Pair<Integer, String>> suffixes;
public SuffixTree(String str) {
if (str.length() < 1) {
return;
}
mainString = str + '$';
//Suffixes List
suffixes = new ArrayList<>();
for (int i = mainString.length() - 2; i >= 0; i--) {
suffixes.add(new Pair<>(i, mainString.substring(i)));
}
//Create Suffix Tree
root = new Node(-1, null);
for (Pair<Integer, String> suffix : suffixes) {
root.insertString(suffix.getKey(), suffix.getValue());
}
}
private class Node {
int index; //-1 means it's a non-leaf node
String value; //Just root value is null
ArrayList<Node> children;
public Node(int index, String value) {
this.index = index;
this.value = value;
this.children = new ArrayList<>();
}
public void insertString(int index, String value) {
int end = 0;
Node found = null;
if (this.value != null) {//non-root
//find shared sub-string
for (end = 0; end < this.value.length(); end++) {
if (this.value.charAt(end) != value.charAt(end)) {
break;
}
}
value = value.substring(end);
}
for (Node node : children) {
if (node.value.charAt(0) == value.charAt(0)) {
found = node;
break;
}
}
if (found == null) {
if (this.index == -1) { //non-leaf (including root at start)
this.children.add(new Node(index, value));
} else { //needs branch
//branch
this.children.add(new Node(this.index, this.value.substring(end)));
this.children.add(new Node(index, value));
this.index = -1;
this.value = this.value.substring(0, end);
}
} else {
found.insertString(index, value);
}
}
}
}