SuffixTree/suffixTree.java at main · Guuhua/SuffixTree · GitHub

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
import java.util.HashMap;

class Node {

    public int start, end;
    public boolean leaf;
    public Node suffix_link;
    public HashMap<Character, Node> children = new HashMap<>();

    public Node (Boolean leaf) { this.leaf = leaf; }
}


/**
 * Suffix tree
 *
*/
public class suffixTree {
    public String T;
    public Node root;
    private Node actNode, insideNode;
    public int len = -1;
    private int actEdge = -1, actLength = 0, remainder = 0;
    private int end = -1;

    public suffixTree(String strs) {
        this.T = strs + "#";
        this.buildTree();
    }

    public int edgelength(Node node) {
        return (node.leaf ? this.end : node.end) - node.start + 1;
    }

    private boolean walkdown(Node node) {
        int length = this.edgelength(node);
        if (this.actLength >= length) {
            this.actEdge += length;
            this.actLength -= length;
            this.actNode = node;
            return true;
        }
        return false;
    }

    private Node genNode(int start, int end, boolean leaf) {
        Node node = new Node(leaf);
        node.suffix_link = this.root;
        node.start = start;
        node.end = end;
        return node;
    }

    private void genTree(int pos) {
        this.end = pos;
        this.remainder += 1;
        this.insideNode = null;

        while (this.remainder > 0) {
            if (this.actLength == 0) {
                this.actEdge = pos;
            }
            if (this.actNode.children.get(this.T.charAt(this.actEdge)) == null) {
                this.actNode.children.put(this.T.charAt(this.actEdge), this.genNode(pos, -1, true));
                if (this.insideNode != null) {
                    this.insideNode.suffix_link = this.actNode;
                    this.insideNode = null;
                }
            }
            else {
                Node nextNode = this.actNode.children.get(this.T.charAt(this.actEdge));
                if (this.walkdown(nextNode)) {
                    continue;
                }
                if (this.T.charAt(nextNode.start + this.actLength) == this.T.charAt(pos)) {
                    if (this.insideNode != null && (this.actNode != this.root)) {
                        this.insideNode.suffix_link = this.actNode;
                        this.insideNode = null;
                    }

                    this.actLength += 1;
                    break;
                }
                int splitEnd = nextNode.start + this.actLength - 1;
                Node splitNode = this.genNode(nextNode.start, splitEnd, false);
                this.actNode.children.put(this.T.charAt(this.actEdge), splitNode);
                splitNode.children.put(this.T.charAt(pos), this.genNode(pos, -1, true));
                nextNode.start += this.actLength;
                splitNode.children.put(this.T.charAt(nextNode.start), nextNode);

                if (this.insideNode != null) {
                    this.insideNode.suffix_link = splitNode;
                }
                this.insideNode = splitNode;
            }
            this.remainder -= 1;
            if (this.actNode == this.root && this.remainder > 0) {
                this.actLength -= 1;
                this.actEdge = pos - this.remainder + 1;
            }
            else if (this.actNode != this.root) {
                this.actNode = this.actNode.suffix_link;
            }
        }
    }

    private void buildTree() {
        this.len = this.T.length();
        int rootEnd = -1;
        this.root = this.genNode(-1, rootEnd, false);
        this.actNode = this.root;
        for (int i = 0; i < this.len; ++i) {
            this.genTree(i);
        }
    }
}