I was wondering why the following implementation of a Suffix Tree is 2000 times slower than using a similar data structure in C++ (I tested it using python3, pypy3 and pypy2). I know the bottleneck is the `traverse` method, do you spot chance of optimisation in the following code? Thanks!

```
from sys import stdin, stdout, stderr, setrecursionlimit
setrecursionlimit(100000)

def read():
    return stdin.readline().rstrip()

def readint():
    return int(read())

def make_node(_pos, _len):
    global s, n, sz, to, link, fpos, slen, pos, node
    fpos[sz] = _pos
    slen[sz] = _len
    sz += 1
    return sz-1

def go_edge():
    global s, n, sz, to, link, fpos, slen, pos, node
    while (pos > slen[to[node].get(s[n - pos], 0)]):
        node = to[node].get(s[n - pos], 0)
        pos -= slen[node]

def add_letter(c):
    global s, n, sz, to, link, fpos, slen, pos, node
    s[n] = c
    n += 1
    pos += 1
    last = 0
    while(pos > 0):
        go_edge()
        edge = s[n - pos]
        v = to[node].get(edge, 0)
        t = s[fpos[v] + pos - 1]
        if (v == 0):
            to[node][edge] = make_node(n - pos, inf)
            link[last] = node
            last = 0
        elif (t == c):
            link[last] = node
            return
        else:
            u = make_node(fpos[v], pos - 1)
            to[u][c] = make_node(n - 1, inf)
            to[u][t] = v
            fpos[v] += pos - 1
            slen[v] -= pos - 1
            to[node][edge] = u
            link[last] = u
            last = u
        if(node == 0):
            pos -= 1
        else:
            node = link[node]

def init_tree(st):
    global slen, ans, inf, maxn, s, to, fpos, slen, link, node, pos, sz, n

    inf = int(1e9)
    maxn = len(st)*2+1 #int(1e6+1)
    s = [0]*maxn
    to = [{} for i in range(maxn)]
    fpos, slen, link = [0]*maxn, [0]*maxn, [0]*maxn

    node, pos = 0, 0
    sz = 1
    n = 0

    slen[0] = inf
    ans = 0
    for c in st:
        add_letter(ord(c))

text = "TTTTTTTTTT" + 1777*"A" + "$"
query = 1750*"A"

def traverse_edge(st, idx, start, end):
    global len_text, len_st
    k = start
    while k <= end and k < len_text and idx < len_st:
        if text[k] != st[idx]:
            return -1
        k += 1
        idx += 1
    if idx == len_st:
        return idx
    return 0

def edgelen(v, init, e):
    if(v == 0):
        return 0
    return e-init+1

def dfs(node, leafs, off):
    if not node:
        return
    k, tree = node
    if not isinstance(tree, int): # it is a node pointing to other nodes
        for kk, value in tree.items():
            if slen[value] > 190000000:
                leafs.append(fpos[value]-off)
            else:
                dfs((kk, to[value]), leafs, off+slen[value])

def traverse(v, st, idx, depth=0):
    global len_st
    result = cache.get((v, st), -2)
    if result != -2:
        return result
    r = -1
    init = fpos[v]
    end = fpos[v]+slen[v]
    e = end-1
    if v != 0:
        r = traverse_edge(st, idx, init, e)
        if r != 0:
            if r == -1:
                cache[(v, st)] = []
                return []
            depth += r
            # Here is when we found a match
            leafs = []
            dfs((v, to[v]), leafs, depth)
            #return reversed(leafs)
            return leafs
    idx = idx + edgelen(v, init, e)
    if idx > len_st:
        cache[(v, st)] = []
        return []
    k = ord(st[idx])
    children = to[v]
    if k in children:
        vv = children.get(k, 0)
        matches = traverse(vv, st, idx, depth)
        cache[(v, st)] = matches
        return matches
    return []

def main():
    global text, len_st, len_text, cache
    init_tree(text)
    len_text = len(text)
    len_st = len(query)
    r = []
    #cache = {}
    for runs in range(1000):
        cache = {}
        matches = traverse(0, query, 0)
        r.append("\n".join(str(m) for m in matches))
    stdout.write("\n".join(r)+"\n")

main()

```