I'm trying to solve this problem using a trie, but I keep getting TLE. The algorithm's complexity is O(L²), so it should pass. Any suggestion about what could be going wrong?

#include <cstdio>
#include <cstring>
#include <vector>
#include <string>

using namespace std;

char s[1001];
int L,best,found[1000];
vector<int> poss;

struct node{
    int cont;
    node *link[4];
    
    node(){
        cont = 0;
        
        for(int i = 0;i < 4;++i)
            link[i] = NULL;
    }
};

struct trie{
    node *root;
    
    trie(){
        root = new node();
    }
    
    void insert(int pos){
        node *p = root;
        string aux;
        
        for(int i = pos,nxt;i < L;++i){
            aux += s[i];
            
            if(s[i] == 'A') nxt = 0;
            else if(s[i] == 'C') nxt = 1;
            else if(s[i] == 'G') nxt = 2;
            else nxt = 3;
            
            if(p->link[nxt] == NULL) p->link[nxt] = new node();
            p = p->link[nxt];
            ++p->cont;
            
            if(p->cont > 1){
                if(i-pos+1 > best){
                    poss.clear();
                    best = i-pos+1;
                }
                
                if(i-pos+1 == best){
                    poss.push_back(pos);
                    found[pos] = p->cont;
                }
            }
        }
    }
};

int main(){
    int TC;
    
    scanf("%d",&TC);
    
    while(TC--){
        scanf("%s",s);
        
        L = strlen(s);
        best = -1;
        
        trie *T;
        T = new trie();
        poss.clear();
        
        for(int i = 0;i < L;++i)
            T->insert(i);
        
        delete(T);
        
        if(best == -1) puts("No repetitions found!");
        else{
            string ans = "Z";
            int ind,sz = poss.size();
            
            for(int i = 0;i < sz;++i){
                int x = poss[i];
                string aux = string(s + x,s + (x+best));
                
                if(aux <= ans){
                    ans = aux;
                    ind = x;
                }
            }
            
            printf("%s %d\n",ans.c_str(),found[ind]);
        }
    }
    
    return 0;
}