UVa 902

From Algorithmist
Jump to navigation Jump to search

902-Password Search

Summary[edit]

Given a string you have to find the most frequently occuring substring of a given length

Explanation[edit]

Usage of maps form STL in C++ will make the problem quite easy. Making a vector/array and counting the frequencies is doomed to time out.

Implementations[edit]

map<string,int>mymap;
map<string,int>::iterator it;
for(i=0;i<str.length()-n+1;i++)
mymap[str.substr(i,n)]++;
for(it=mymap.begin();it!=mymap.end();it++)
{
if((*it).second>max){res=(*it).first;max=(*it).second;}
}
cout<<res<<endl;

Input[edit]

1 thequickbrownfoxjumpsoverthelazydog
3 thequickbrownfoxjumpsoverthelazydog
4 testingthecodetofindtheerrortestandtestagain
5 thearraycanbetoobigsobecarefulandtherecantberarecasescanbe

Output[edit]

o
the
test
canbe