import java.util.*;

public class ParseHtml {
    /*
    *
input aa<a>bbb<b>ccc</b>gg</a>zzz
output :
1. aa
2. a: bbb
3. a+b: ccc
4. a: gg
5. zzz
    * */
    public static void main(String[] args){
        ParseHtml parseHtml = new ParseHtml();
        String input = "aa<a>bbb<b>ccc</b>gg</a>zzz";
        try {
            List<HtmlText> list = parseHtml.parseSeq(input);
            for (int i = 0; i < list.size(); i++) {
                HtmlText text = list.get(i);
                System.out.println(text.content + " " + text.tags);
            }
        } catch (Throwable t) {
            System.out.println(t);
        }
    }

    public List<HtmlText> parseSeq(String input) throws Exception {
        StringBuilder value = new StringBuilder();
        ArrayList<String> tags = new ArrayList<>();
        ArrayList<HtmlText> ans = new ArrayList<>();
        Stack<String> sk = new Stack<>();
        int idx = 0, N = input.length();
        while (idx < N) {
            char cur = input.charAt(idx);
            if (cur == '<') {
                if (value.length() > 0) {
                    ans.add(new HtmlText(value.toString(), new HashSet<String>(tags)));
                }
                value = new StringBuilder();
                Pair<String, Integer> pair = getTag(input, idx);
                if (isOppositeTag(pair.a)) {
                    if (sk.isEmpty()) throw new Exception("syntax error: only / tag " + pair.a);
                    String tag = sk.pop();
                    if (!isMatchOppositeTag(tag, pair.a)) {
                        throw new Exception("syntax error: " + pair.a + " not match any tag");
                    } else {
                        tags.remove(tags.size() - 1);
                    }
                } else {
                    tags.add(pair.a);
                    sk.add(pair.a);
                }
                idx = pair.b + 1;
            } else {
                value.append(cur);
                idx++;
            }
        }
        if (!tags.isEmpty()) {
            throw new Exception("syntax error: " + tags + " not match any tag");
        }
        if (value.length() > 0) {
            ans.add(new HtmlText(value.toString(), new HashSet<>()));
        }
        return ans;
    }

    private boolean isOppositeTag(String a) {
        return a.contains("/");
    }
    private boolean isMatchOppositeTag(String a, String b) {
        int aIdx = 0, bIdx = 0;
        while (aIdx < a.length() && bIdx < b.length()) {
            char aChar = a.charAt(aIdx);
            char bChar = b.charAt(bIdx);
            if (aChar == '/') {
                aIdx++;
            } else if (bChar == '/') {
                bIdx++;
            } else if (aChar != bChar) {
                return false;
            } else {
                aIdx++;
                bIdx++;
            }
        }
        return aIdx == a.length() && bIdx == b.length();
    }

    private Pair<String, Integer> getTag(String input, Integer curIdx) throws Exception {
        if (input.charAt(curIdx) != '<') throw new Exception("tag doesn't start from <");
        curIdx++;
        String ans = "";
        while (input.charAt(curIdx) != '>') {
            ans += input.charAt(curIdx++);
        }
        return new Pair(ans, curIdx);
    }
}

class Pair<A, B> {
    A a;
    B b;
    Pair(A a, B b) {
        this.a = a;
        this.b = b;
    }
}

class HtmlText {
    String content;
    Set<String> tags;
    HtmlText(String a, Set<String> b) {
        this.content = a;
        this.tags = b;
    }
}

output

aa []
bbb [a]
ccc [a, b]
gg [a]
zzz []

    public static void main(String[] args) {
        TestQ tt = new TestQ();
        tt.test2(5, 2, 4);
        System.out.println("======");
        tt.test2(5, 2, 3);
    }

    public void test2(int N, int X, int Y) {
        Graph graph = new Graph();
        for (int i = 1; i <= N; i++) {
            Node node = new Node(i);
            graph.map.put(i, node);
        }
        int tmp = Y, tmp1 = X;
        Y = Math.max(tmp, tmp1);
        X = Math.min(tmp, tmp1);
        Node node1 = graph.map.get(X);
        Node node2 = graph.map.get(Y);
        Edge edge;
        edge = new Edge(node1, node2, 1);
        node1.edges.add(edge);
        graph.edges.add(edge);

        for (int k : graph.map.keySet()) {
            Node node = graph.map.get(k);
            Node nextNode = graph.map.get(node.value + 1);
            if (nextNode == null) continue;
            if (nextNode.value == Y && node.value == X) continue;
            Edge ee = new Edge(node, nextNode, 1);
            node.edges.add(ee);
            graph.edges.add(ee);
        }
        int ans = 0;
        for (int i = 0; i < graph.edges.size(); i++) {
            if (graph.edges.get(i).cost == 1) {
                ans++;
            }
        }
        System.out.println("1 : " + ans);
        for (int dis = 2; dis < N; dis++) {
            int tmpAns = 0;
            for (Integer k : graph.map.keySet()) {
                Node node = graph.map.get(k);
                tmpAns += traverse(node, dis, X, Y);
            }
            System.out.println(dis + " : " + tmpAns);
        }
    }

    public int traverse(Node curNode, int dis, int X, int Y) {
        if (dis == 0) {
            return 1;
        }
        if (curNode.value == X && curNode.value + dis >= Y) {
            //fast
            List<Edge> edges = curNode.edges;
            Node nextNode = null;
            for (int fi = 0; fi < edges.size(); fi++) {
                if (nextNode == null) {
                    nextNode = edges.get(fi).e;
                } else if (nextNode.value < edges.get(fi).e.value) {
                    nextNode = edges.get(fi).e;
                }
            }
            if (nextNode == null) {
                return 0;
            }
            return traverse(nextNode, dis - 1, X, Y);
        } else {
            // slow
            List<Edge> edges = curNode.edges;
            int tmp = 0;
            for (int fi = 0; fi < edges.size(); fi++) {
                Node nextNode = edges.get(fi).e;
                tmp += traverse(nextNode, dis - 1, X, Y);
            }
            return tmp;
        }
    }


public class Edge {
    Node s;
    Node e;
    int cost = 0;

    Edge(Node s, Node e, int cost) {
        this.s = s;
        this.e = e;
        this.cost = cost;
    }

}
public class Node {
    int value = -1;
    List<Edge> edges = new ArrayList<>();
    public Node(int value) {
        this.value = value;
    }

}

public class Graph {
    Map<Integer, Node> map = new LinkedHashMap<>(); //1:node, 2: node
    List<Edge> edges = new ArrayList<>();// 1-2, 2-3
}

output

1 : 5
2 : 4
3 : 1
4 : 0
======
1 : 4
2 : 3
3 : 2
4 : 1