Strings In Text Cells Of Lookup Table To Inform Conditional Formatting

I have a 1000x1000 cell grid on one of the worksheets in my workbook where each cell contains one of the following four possibilities:

1) Blank
2) A string that is not defined in a lookup table (*lookup table = a named range on a different sheet)
3) A string that exactly matches an item in the lookup table
4) A long string that contains an item in the lookup table (which can be found with a FIND function, for example)

I would like to apply conditional formatting to my 1000x1000 grid, to color each cell according to the lookup table, where the last column has the name of a color that I can match with my conditional formatting setup.

I have solved everything except for No. 4).

2) is taken care of by using "Format only cells that contain" with "No Blanks"

My solution for 3) - using "Use a Formula to Determine Which Cells to Format" - uses
=VLOOKUP(A1,lookup_table,2,FALSE)="fill color name" So, for every different color I want to use, I have a different Formatting Rule in the Conditional Formatting dialog.

But 4) is tricky, because VLOOKUP can only return the result for a specific cell value.
If my cell contains France;Germany;Italy, I'd like the color to be according to what I set for "France" in my lookup table. Or, if my cell contains Germany;France;Italy, I'd like it to be set based on what I decided Germany is in the lookup table (i.e. "blue").

You can notice that one thing that is consistent is that I separate my "sub-strings" that are contained in the lookup table with a semi-colon.

So, one way might be to see if FIND finds a semi-colon, and then grab the string that goes before that character position.