UVA 11512 Solution

/* Solution of uva-11512 using map and Trie */

#include<iostream>
#include<map>
#include<string>
#include<string.h>

using namespace std;
int trie[501500][4];
char newarr[1005],ch[1005];
int idx,ll;

bool createTrie(string s)
{
strcpy(ch,s.c_str());
int ci=0,li=0,i,j,k;
k=0;
ll=0;
bool flag=false;
for(i=0;ch[i];i++)
{
switch(ch[i])
{
case 'A':
j=0;
break;

case 'C':
j=1;
break;

case 'G':
j=2;
break;

case 'T':
j=3;break;
}
if(trie[ci][j]==0)
{
idx++;
trie[ci][j]=idx;
ci=idx;
}
else
{
ci=trie[ci][j];
newarr[k]=ch[i];
k++;
newarr[k]='\0';
flag=true;
ll++;
}
}
return flag;
}
int main()
{
int test,i,j,len,y,l,val,vl;
string str,input,output;
cin>>test;
map<string,int> mymap;
map<string,int>::iterator it,it2;
bool flag;
while(test--)
{
cin>>str;
len=str.size();
idx=0;
l=len;
flag=true;
val=0;
memset(trie,0,sizeof(trie));
mymap.clear();
vl=0;
for(i=0;i<len;i++)
{
if(vl>l)
break;
input=str.substr(i,l);
l--;
if(createTrie(input))
{
string s(newarr);
if(flag)
{
output.assign(s);
mymap.insert(make_pair<string,int>(output,2));
flag=false;
val=2;
vl=output.size();
}
else
{
y=output.size();
if(ll>y)
{
mymap.clear();
mymap.insert(make_pair<string,int>(s,2));
output.assign(s);
val=2;
vl=output.size();
}
else if(ll==y)
{
it=mymap.find(s);
it2=mymap.find(output);
if(it==mymap.end())
{
mymap.insert(make_pair<string,int>(s,1));
it=mymap.find(s);
}
it->second++;
if(it->second>=it2->second && s<=output)
{
output.assign(s);
val=it->second;
vl=output.size();
}
}
}
}
}
if(val==0)
cout<<"No repetitions found!\n";
else
cout<<output<<" "<<val<<endl;
}
return 0;
}