The technique you're looking for is Acoustic Fingerprinting [1]. There's a pretty easily understandable python implementation[2] of it if you're interested. In Shazam's case it is looking for peaks in the sound's spectrograph, so I don't think it would likely confuse two songs based on melody alone. It would have to be very close in rhythm, melody, and possibly even be in the same key.

[1] - https://en.wikipedia.org/wiki/Acoustic_fingerprint [2] - https://github.com/worldveil/dejavu

From my understanding, Shazam can differentiate between songs that share samples by doing classification on a windowed section of input. I.e, take 5 seconds of recording, and classify on t=0..2, 1..3, 2..4, 3..5. The idea being that the sample usage won't continue forever, and you will eventually get a new pattern. (You can even use your classifications from t=0..2 as priors for future classifications!).

For an easy intro to how Shazam works, see this: https://www.toptal.com/algorithms/shazam-it-music-processing...