CareerCup

<a href="http://www.softwareinterviewqna.com/blog/?p=1">The approach to this problem is divide-and-conquer.</a>

Suffix Tree

I do not think suffix tree can do it.

i guess one of the (best)ways assuming hashtables are allowed and the string is not too large, just anagram the string to get all the possible parts (anagrams); throw the anagrams into a hashtable with each anagram as key. now, for any input for a match check, simply check if the input is a key in the hastable in which case you return a true/match else a false/no-match...

Why anagrams? I interpreted the problem as doing a substring match with possible typos (hence the 'score' requirement).

Use Naive Bayes Algorithm, it will output the probability of the match. It assumes that each word is independent of each other.

typedef struct _match {
int position;
int score;
} match;

std::list<match> get_matches(char *sstr, char *input) {
std::list<match> result;
int score = 0;
int position = 0;
char* input_buffer;
char* sstr_buffer;

while(*input) {
score = 0;
input_buffer = input;
sstr_buffer = sstr;
while(*(input++) == *(sstr++)) {
score++;
}
if(score) {
match new_match;
new_match.position = position;
new_match.score = score;
result.push_back(new_match);
}
input = ++input_buffer;
sstr = sstr_buffer;
position++;
}
return result;
}

I think this is similar to longest common subsequence problem.

i would say..suffix tree...cause it sounds like a substring problem rather than a subsequence problem

isnt this simple edit distance(dynamic programming)

check for smith waterman algorithm