Subsequence-Free Substrings

You are given two strings s and t of lowercase English letters.

A contiguous substring of s contains t as a subsequence if the characters of t appear in the substring in order, not necessarily adjacently.

Return the number of non-empty contiguous substrings of s that do not contain t as a subsequence. Substrings starting or ending at different indices are counted separately even when their text is identical.

Examples

Example 1

Input: s = "abcab", t = "ab"
Output: 8
Explanation: Of the 15 non-empty substrings, 7 contain "ab" as a subsequence
(for instance "ab" at index 0, "abc", "abca", "abcab", "bcab", "cab", "ab" at
index 3). The remaining 8 do not.

Example 2

Input: s = "aaa", t = "b"
Output: 6
Explanation: "b" never occurs, so all 6 substrings qualify.