It is simple. You need any address, not some specific address. For example, you can generate any address with the first matching letter, whatever it will be. How many addresses you need on average? In case of base58, it will be sqrt(58), so something around 8. Let's try:
privkey=1, address=1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm
privkey=2, address=1LagHJk2FyCV2VzrNHVqg3gYG4TSYwDV4m
privkey=3, address=1NZUP3JAc9JkmbvmoTv7nVgZGtyJjirKV1
privkey=4, address=1MnyqgrXCmcWJHBYEsAWf7oMyqJAS81eC
privkey=5, address=1E1NUNmYw1G5c3FKNPd435QmDvuNG3auYk
Got it. Five shots and you have 1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm and 1E1NUNmYw1G5c3FKNPd435QmDvuNG3auYk with matching "1E". You can repeat the same for two chars, three chars, and so on. In general, you need a square of the number of all combinations, because you need
any address, not
specific address. It is a huge difference, because there are more possible solutions, so it is more likely that you will hit something along the way. It is counterintuitive, but it can be really simplified to a birthday paradox: you understand that paradox or not, maybe it is a matter of trying pairgen vs vanitygen and seeing why pairgen is so fast.
Don't you hash a script in P2SH?
Yes, you hash a script, but it doesn't matter what is hashed, if you have 160-bit hash, then you can reach collisions after trying 2^80 hashes, whatever you hash.
Whether that contains multiple public keys or just one.
This attack is quite simple: you create two scripts, one is "
OP_CHECKSIG" and another is "2 2 OP_CHECKMULTISIG". You try different first and second private keys, trying to get a collision. After trying around 2^80 addresses, there is a chance to find one pair of scripts that will hash to the same value, then you can attack. You can try around 2^32 addresses on your CPU and see that you will probably hit some P2SH script pair, where the first 64 bits will be the same. 
