If you define "substring" fairly rigidly as say, "group of non-whitespace characters bounded at each end by whitespace" (ie, whole words), then limit substring searching to whole words only (no phrases, no partial words), then you could augment your main dictionary with another dictionary of all the words (an index, if you will). "Substring" searches (eg "lonely") would then be a matter of looking up the index. (Each time a song is added to the playlist, you'd need to generate index data for it; and right at the start you'd need to index everything already in there.)

Of course, the limitation of this is that you can only do substring matches on whole words (eg "lonely", not "onel"), and can't do substring matches on phrases ("lonely hearts") -- although these could be faked by looking up the index for each word in the phrase and returning only the results that match all words ("lonely" and "hearts").

This is coming close to implementing your own database, so if you need much more than this you're probably better off investing the effort in moving to a database rather than reinventing one (at which point, depending on your chosen database, you get real substring indexing and so on for "free").