### MarioYC's blog

By MarioYC2 years ago, ,

I'm trying to solve this problem using a trie, but I keep getting TLE. The algorithm's complexity is O(L2), 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(){
cont = 0;

for(int i = 0;i < 4;++i)
}
};

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;

++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;
}
```

•
• +5
•

 » 20 months ago, # |   0 It should be suffix array, or use trie to construct a DFA.

 » 20 months ago, # |   0 IMHO the problem is in line 'aux += s[i]'. Since you don't even use variable 'aux' you may consider removing it.