I would go with hashing. Usually, since this sounds like an algorithms homework problem, in my experience, we were not allowed to answer with hashing beacause it really depends on your hash function. If it is not good enough, then you won't get unique values for each string.

I would build the list of strings into a binary sort tree based on the characters in the string. Maintaining an algorithm that says if the string comes before the head node in alphabetical order, place it to the left, and if it comes after the head node, place it to the right. Recursively of course. We have a tree. Now granted worst case this will be completed in O(n) time, which would just effectively be a linked list, but with a good head node, somewhere in the m or n area, this lookup can be completed in O(log n). So the whole operation would take O(n log n) time.

Your provided algorithm, worst case would take O(n^2). Let's say every string was 30 characters, and ended with K and began with L. All excpet the 2nd to last character. Effectively we would search 28 characters of all the provided strings. The n^2 comes into play with finding the size of all the strings. Each string would take O(n) time making it an n^2 algorithm. In my algorithm, we are halving the problem each time, which provides a lot quicker of a search.

`M28K`

at all.