Suffix Tree in Python

So, about all those globals. They make your code really hard to read, I have almost no idea what is going on (after having read it twice). The general recommendation is to only use global objects if you really have to. Otherwise pass the objects either as arguments to the function, or write a class which has the relevant variables as attributes and keep the state like this.

Another thing that makes your code a lot easier to understand (both for other people and for yourself in two months time), are docstrings, which document what each function does, the parameters it takes and what it returns or modifies.

I finally gave up trying to optimize Pypy and wrote the code I needed just in C++. Here is it in case somebody is curious:

#include <bits/stdc++.h>

using namespace std;

#define fpos adla
const int inf = 1e9;
const int maxn = 1e6+1;
//#define maxn 100005

char s[maxn];
map<int,int> to[maxn];
int slen[maxn], fpos[maxn], link[maxn];
int node, pos;
int sz = 1, n = 0;

int text_len;
char text[maxn];
int query_len;
char query[maxn];

int make_node(int _pos, int _len) {
    fpos[sz] = _pos;
    slen[sz] = _len;
    return sz++;
}

void go_edge() {
    while(pos > slen[to[node][s[n - pos]]]) {
        node = to[node][s[n - pos]];
        pos -= slen[node];
    }
}

void add_letter(int c) {
    s[n++] = c;
    pos++;
    int last = 0;
    while(pos > 0) {
        go_edge();
        int edge = s[n - pos];
        //int &v = to[node][edge];
        int v = to[node][edge];
        int t = s[fpos[v] + pos - 1];
        if(v == 0) {
            //v = make_node(n - pos, inf);
            to[node][edge] = make_node(n - pos, inf);
            link[last] = node;
            last = 0;
        }
        else if(t == c) {
            link[last] = node;
            return;
        }
        else {
            int 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;
            // v = u;
            to[node][edge] = u;
            link[last] = u;
            last = u;
        }
        if(node == 0)
            pos--;
        else
            node = link[node];
    }
}

int traverse_edge(char st[], int st_len, int idx, int start, int end) {
    int k = start;
    while (k <= end && k < text_len && idx < st_len) {
        if (text[k] != st[idx]) {
            return -1;
        }
        k += 1;
        idx += 1;
    }
    if (idx == st_len) {
        return idx;
    }
    return 0;
}

int edgelen(int v, int init, int e) {
    if (v == 0) {
        return 0;
    }
    return e-init+1;
}

void dfs(map<int, int> tree, vector<vector<int>> leafs, int off) {
    if (tree.empty()) {
        return;
    }
        /* for ( auto [k, value] : tree) { */ // C++17
        for ( auto it : tree) {
            int value = it.second;
            if (slen[value] > maxn / 10) {
                vector<int> leaf;
                leaf.push_back(fpos[value]);
                leaf.push_back(slen[value]);
                leaf.push_back(fpos[value]-off);
                leafs.push_back(leaf);
            } else {
                dfs(to[value], leafs, off+slen[value]);
            }
        }
}

pair<bool, vector<int>> traverse(int v, map<int,int> tree, char st[], int idx, int depth) {
    int r = -1;
    int init = fpos[v];
    int end = fpos[v]+slen[v];
    int e = end - 1;
    if (v != 0) {
        r = traverse_edge(st, query_len, idx, init, e);
        if (r != 0) {
            if (r == -1) {
                return {false, vector<int>{}}; 
            }
            vector<int> matches;
            return {true, matches};
        }
    }
    idx = idx + edgelen(v, init, e);
    if (idx > query_len) {
        return {false, vector<int>{}}; 
    }
    int k = int(st[idx]);
    map<int,int> children = to[v];
    /* if (children.contains(k)) { */ // C++20 
    if (children.find(k) != children.end()) {
        int vv = tree[k];
        return traverse(vv, to[vv], st, idx, depth);
    }
    return pair<bool, vector<int>>(false, vector<int>{});
}


int main() {
    int t;
    scanf("%d", &t);
        while (t--) {
            scanf("%s", text);
            text_len = strlen(text);

            for (int i=0; i<maxn; i++) {
                to[i] = map<int,int>{};
            }
            sz = 1;
            n = 0;
            pos = 0;
            node = 0;
            slen[0] = inf;

            for (int i=0; i<text_len; i++) {
                add_letter((int)text[i]);
            }
            add_letter((int)'$');

            int q;
            scanf("%d", &q);
                while (q--) {
                    scanf("%s", query);
                    query_len = strlen(query);
                    pair<bool, vector<int>> results = traverse(0, to[0], query, 0, 0);
                    printf("%s\n", results.first ? "y" : "n");
                }
        }
}
```