Finding the longest dictionary word at the end of a string

I'm looking for the best way to search a string of alphabetical characters for the longest possible dictionary word at the end of the string.

Example: For the string qbehugejackhammer the result should be jackhammer instead of hammer.

One way to do this somewhat efficiently would be storing the words in reversed form in an indexed table and iterating them one letter at a time until it no longer matches anything:

SELECT word FROM dictionary WHERE word LIKE 'remmahkca%';
SELECT word FROM dictionary WHERE word LIKE 'remmahkcaj%'; # last match
SELECT word FROM dictionary WHERE word LIKE 'remmahkcaje%';

That looks and feels like a hack and is most likely not the optimal solution. Is there any faster and/or nicer way to do this? My tools of choice are PHP and MySQL but if some other language or DBMS suits my needs better I'm开发者_JS百科 all ears.

You could start by searching for a word that matches the entire string and keep removing letters at the beginning of the string until you find a match:

SELECT word FROM dictionary WHERE word = 'qbehugejackhammer'; --no match
SELECT word FROM dictionary WHERE word = 'behugejackhammer'; --no match
SELECT word FROM dictionary WHERE word = 'ehugejackhammer'; --no match
SELECT word FROM dictionary WHERE word = 'hugejackhammer'; --no match
--...
SELECT word FROM dictionary WHERE word = 'jackhammer'; --found it!

It may sound slightly evil, but you'll probably get best performance by loading your dictionary into an array in the shape of a dictionary tree, but in reverse word order, for example:

array(
    'r' => array(
        'u' => array(), // -- words ending in 'ur' would end up in here
        'a' => array(), // -- words ending in 'ar' would end up here
        'e' => array( // -- words ending in 'er' would end up in here
            'm' => array(
                'm' => array(
                      // -- jackhammer will be kept further up here

Then seeking up.

$reverseWord = ""; // -- Incoming 'word' string goes here, in reverse.
$dictionary = [structure above];
$dictionaryPosition = $dictionary;
$dictionaryHistory = "";

for( $i = 0, $l = strlen($reverseWord); $i < $l; $i++ ) {
    $char = $reverseWord[$i];

    // -- If this character doesn't exist in this dictionary position, we've reached the end
    if( !isset($dictionaryPosition[$char]) )
        break;

    // -- log this character
    $dictionaryHistory = $char . $dictionaryHistory;

    // -- Climb up the tree
    $dictionaryPosition = $dictionaryPosition[$char];
}

// -- $dictionaryHistory now contains the word you're looking for.

Each array should contain no more than 26 entries (assuming alphabetic characters only), so you're looking at doing, at most, 26*n lookups of a single character each. Even with a word depth of 20 characters, that's infinitely better than iterating through a list of 50k words several times.

A quick hacky answer: load your dictionary into a map or whatever the php equivalent data structure is (An english dictionary is only ~50k words, fits in RAM v easily, and a map is much, much faster to query than a DB call). Then iterate forwards 1 character at a time, testing each substring against the map until you find a match.

Depending on how long your strings are, you could optimise by first checking the longest word in the dictionary (you can get this during the dictionary load) and starting the appropriate distance in. I'm sure there are other similar optimisations you could employ too (longest by start character etc)

Edit: "map" should be "set".

Load the dictionary a PHP array. For every input word, use in_array (link) on successively smaller substrings as explained below till you find a match.

For example, consider your input qbehugejackhammer. First, search the array for qbehugejackhammer, then for behugejackhammer, then for ehugejackhammer and so on till you find a match. You can stop as soon as you find the first match.