Тут вступаем на скользкую почву, mysql я видел один раз лет десять назад :)
Исходя из общих соображений, однако (решение в лоб):
SELECT UNIQUE s.string
FROM strings s
JOIN templates t ON s.string LIKE t.template
Если в мускуле можно делать селекты прямо из коллекций, пусть strings будет такой коллекцией, если нет — писать строки во временную таблицу.
С join condition можно поэкспериментировать, например использовать regexp_like (или как это нызвается в mysql?)
