I thought they use Cepstrum followed by machine learning.
fingerprints stored in a scalable lsh style lookup table. (iirc) with the goal of a fast, scalable lookup table for all the 30s windows in all recorded music.
Could you use something like a dynamic time warping algorithm for this? (I'm not super acquainted with the technique and not sure if you could get away with it in the frequency domain used for the matching.)