Разбить строку на непересекающиеся подстроки

вот условие задачи, второй день пытаюсь ее решить, но идей так и не появилось , подтолкните меня к ответу, любу скиньте готовое решение на python, спасибо

Входные данные
Длину строки q обозначим как |q| (|abac| = 4, |sam| = 3). Во входном файле содержатся 3 строки s, t1, t2 (|s| = |t1| + |t2|, 1 ≤ |t1|, |t2| ≤ 1 000). Все строки содержат только маленькие латинские буквы.

Выходные данные
Подстрокой p[l, r] назовем строку, состоящую из символов pl, pl + 1, ..., pr - 1, pr, где pi — i-тый символ строки p («cde» является подстрокой строки «abcdef», «bcf» — не является).

Тогда любую строку p можно представить в виде разбиения на не пересекающиеся подстроки p[x0 + 1, x1] + p[x1 + 1, x2] + p[x2 + 1, x3] + ... + p[xn - 1 + 1, xn], где 0 = x0 < x1 < x2 < ... < xn - 1 < xn = |p|. При этом длиной разбиения будем называть количество чисел xi, то есть число n.

В данной задаче требуется найти разбиение строки s такое, чтобы из получившихся подстрок можно было сложить строки t1 и t2, не нарушая порядка, в котором подстроки шли в исходной строке. Например, из строки «adbc» нельзя будет выложить слова «cad» и «b», так как порядок подстрок «ad» и «c» будет нарушен.

Программа должна выдавать на экран одно число — минимально возможную длину такого разбиения, то есть количество разрезов, которые потребуется сделать убийце.

Гарантируется, что существует разбиение строки s хотя бы одним способом, чтобы получились строки t1 и t2.

Примеры тестов
входные данные
stopgame
sam
topge
выходные данные
3

входные данные
ababbaba
abbb
abaa
выходные данные
4

Примечание
В первом примере из условия строку можно разрезать следующим образом:
stopgame s|topg|am|e.

Во втором примере:
ababbaba ab|abb|a|b|a.