Finding the longest dictionary word at the end of a string

Question

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 all ears.

Answer 1

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!