Algorithm: Extract keyword from string by database

There are two parts to this problem. The hard part is identifying artist and title. You've got all sorts of variations:

• Beatles, The - Imagine
• The Beatles - Imagine
• Imagine - The Beatles
• The Beatles, Imagine
• Imagine, The Beatles
• Imagine - Beatles, The

Others will include album too:

• Imagine - Imagine - The Beatles

If you have these as a random mismash then you're going to have a hard time dealing with that - normalizing this data into fields is going to require a database of "track names" and "artist names" to attempt to match with, and a lot of guesswork.

What I'd do is ignore the whole mess and throw it at a full text search engine.

test=> select to_tsvector('simple', 'Beatles, The - Imagine');
           to_tsvector           
---------------------------------
 'beatles':1 'imagine':3 'the':2
(1 row)

test=> select to_tsvector('simple', 'Beatles, The - Imagine') @@ to_tsquery('simple', 'Beatles');
 ?column? 
----------
 t
(1 row)

If you were able to turn this into field-separated normalized data, your searches would become much more powerful as you could do weighted matches on fields using setweight, ts_rank, tsvector concatenation with ||, etc.

In principle, if any record in your database could contain your search string then you are going to have to search every record in your database.

What you can do is to use something like the Rabin-Karp algorithm to search for a lot of same-length versions of your search string simultaneously: "Beatles The", "The Beatles". If you ignore spaces and/or punctuation then you might be able to reduce the number of passes even more: "The Beatles", "Beatles, The", "Beatles The". All the examples in Craig Ringer's answer are the same length if you count only letters; you could find all those matches with a single pass through the database using Rabin-Karp