My brother implemented this algorithm in Matlab for his thesis project a few years ago. It's impressively accurate even short snippets of low quality recordings.
Too bad the people who own the patents are so stupid, even going after a guy who posted a blog post explaining how the algorithm worked...
NB: Shazam is run by raging assholes who like to threaten people posting code on their site to implement the algo described in the paper [1:4]. Roy's site is still up, but you may introduce quite a lot of stress into your life by messing around with this interesting paper / technique.
In more interesting news, see [5] for a similar implementation in matlab, and [6] for Roy's java implementation.
You're actually thinking of another company, Landmark Digital. They are the ones who own the algorithm now, not Shazam. I know this because I actually worked at Landmark! That was quite some time ago. And even then, I was of course not authorized to talk about this. So I won't. If it makes you feel any better, Landmark Digital is in the process of being dismantled. Everybody there is getting absorbed back into their corporate parent, the music industry company BMI.
I worked with Avery Wang, the guy who wrote the music recognition algorithm. I took his code and wrote servers and stuff around it, for Landmark's own ends.
Too bad the people who own the patents are so stupid, even going after a guy who posted a blog post explaining how the algorithm worked...