Найти все "разбросанные подстроки" строки

Question

У меня следующая проблема: учитывая две строки v и w, я хочу посчитать вхождения v как «разбросанное подслово» w. Следующий пример должен проиллюстрировать вопрос: Let v = "aa" and w = "abaab". Тогда ответом на мой вопрос будет 2, потому что v встречается два раза: позиции 1 и 3 и позиции 3 и 4 в w.

Кто-нибудь знает хороший способ подсчитать это в Python / sagemath?

Answer 1

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

Построить двумерный массив с размером len(v)+1 на len(w)+1, где dp[i][j] означает число "разбросанные подстроки "v[:i] в w[:j].

• Первоначально dp[0][j] = 1, потому что в каждой строке содержится пустая строка, и dp[i][0] = 0 для i > 0, поскольку в непустой строке нетпустая строка.
• Рассеянная подстрока v[:i+1] в w[:j+1] является либо рассеянной подстрокой v[:i+1] в w[:j], либо, если v[i] == w[j], это также может быть рассеянная подстрока v[:i] в w[:j]. Таким образом, отношение повторения равно dp[i+1][j+1] = dp[i+1][j] + (dp[i][j] if v[i] == w[j] else 0).
• Конечный результат равен dp[len(v)][len(w)].