How to optimise INDEX(MATCH()) for large data sets?

Hello!

Bit of a weird one, I have a working formula but I now want to use it to search across a large dataset so I need to optimise the formula.
Basically I am searching for then returning a sub-string within a string. Problem is I have an array of 65 sub-strings to check within a set of 200,000 input strings.

I have attached the file with some example data Book1.xlsx

I am using this array (ctr+shft+entr) formula: =INDEX($C$2:$C$3,MATCH(1,COUNTIF(A2,"*"&$C$2:$C$3&"*"),0))

As in the attached excel:
Column A (Input String)
1dog
2cat
dog3again
4catfish

Column B Result (Formula)
dog
cat
dog
cat

Column C (sub-string array)
dog
cat

Is there any way this kind of search can be run on this scale? Right now it is taking about 6mins/10,000 rows (but also crashing now and again)

Cheers,
Dan

Awesome! From 6 minutes to 6 seconds! Thank you humdingaling