Skip to content

Instantly share code, notes, and snippets.

@rajatkhanduja
Created October 26, 2012 13:27
Show Gist options
  • Save rajatkhanduja/3958818 to your computer and use it in GitHub Desktop.
Save rajatkhanduja/3958818 to your computer and use it in GitHub Desktop.
My attempt at solving the find strings question on InterviewStreet (https://www.interviewstreet.com/challenges/dashboard/#problem/4efa210eb70ac)
/* Solution using suffix trees. */
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cassert>
using namespace std;
#define ALPHABETSIZE 26
class SuffixTree
{
public:
SuffixTree (bool isRoot = true);
void insertSuffixes (const string& mString);
int getUniqueSubstrings () { return nChildren;}
string kthSmallestSubs (int k);
private:
int insert (const string& suffix, int position);
bool initializeChild (int i)
{
if (this->children[i])
return true;
else
{
this->children[i] = new SuffixTree(false);
return false;
}
};
/* Private members */
bool isRoot;
SuffixTree* children[ALPHABETSIZE];
int nChildren; // Holds the total number of children
};
SuffixTree::SuffixTree(bool isRoot)
{
this->isRoot = isRoot;
bzero (children, sizeof (SuffixTree*) * ALPHABETSIZE);
nChildren = 0;
}
int SuffixTree::insert (const string& suffix, int position)
{
if (position == suffix.length())
{
return 1 + nChildren;
}
int childIndex = suffix[position] - 'a';
int tmpChildren = 0;
if (this->initializeChild (childIndex))
tmpChildren = this->children[childIndex]->getUniqueSubstrings() + 1;
nChildren += (this->children[childIndex]->insert (suffix, position + 1)
- tmpChildren);
return nChildren + 1;
}
void SuffixTree::insertSuffixes (const string& mString)
{
for (int i = 0; i < mString.length(); i++)
{
this->insert (mString, i);
// cout << "Inserting " << mString.substr (i) << endl;
}
}
string SuffixTree::kthSmallestSubs(int k)
{
// cerr << "k = " << k << "; unique subs : " << this->nChildren << endl;
if (k > this->getUniqueSubstrings())
{
return string("INVALID");
}
else
{
int tmp, i;
for (i = 0; i < ALPHABETSIZE; i++)
{
if (NULL == this->children[i])
continue;
if (k > (tmp = 1 + this->children[i]->nChildren))
{
k -= tmp;
}
else
{
break;
}
}
if (i >= ALPHABETSIZE)
{
// cerr << "i = " << i << "; k = " << k << "; tmp = " << tmp << endl;
assert (0);
}
if (k == 1)
{
return string (1, i + 'a');
}
else
{
string t = this->children[i]->kthSmallestSubs(k - 1);
return t.insert (0, 1, i + 'a');
}
}
}
int main (void)
{
int n;
string in;
cin >> n;
SuffixTree sTree;
while (n--)
{
cin >> in;
sTree.insertSuffixes(in);
}
int q, k;
cin >> q;
// cout << sTree.getUniqueSubstrings();
while (q--)
{
cin >> k;
cout << sTree.kthSmallestSubs(k) << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment