Z3 недавно прекратил поддержку интерполантов, и вряд ли они добавят его обратно в ближайшее время.
MathSAT поддерживает интерполанты, но я не думаю, что он поддерживает строки.
Я не знаюНе думаю, что сейчас есть какой-либо SMT-решатель, который поддерживает как строки, так и интерполяции.