Suppose we delete one contiguous part from \(T\). Then the remaining string is a concatenation of a prefix of \(T\) and a suffix of \(T\).

Therefore, for a substring of \(S\) to be valid, its front part must match a prefix of \(T\), and its back part must match a suffix of \(T\).

In the following, we use \(0\)-indexed positions.

Consider a substring \(S[s..e]\). Suppose we split it at position \(c\) as

\[ S[s..c] + S[c+1..e]. \]

Here, the left part is matched with a prefix of \(T\), and the right part is matched with a suffix of \(T\).

Let \(F_s\) be the LCP length of \(T\) and \(S[s..]\). This can be computed from the Z-array of \(T\#S\).

Similarly, let \(B_e\) be the common suffix length of \(T\) and \(S[..e]\). This can be computed in the same way after reversing both strings.

For fixed \(s,e\), the left part matches a prefix of \(T\) if

\[ c \le s+F_s-1. \]

Also, the right part matches a suffix of \(T\) if

\[ c \ge e-B_e. \]

Since either side may be empty, we allow \(c=s-1\) and \(c=e\). Thus, the possible split positions are

\[ [s-1,\ s+F_s-1]\cap[e-B_e,\ e]. \]

The deleted part of \(T\) must have positive length, so the remaining string must have length at most \(M-1\). Hence, for fixed \(s\), the possible endpoints are

\[ s \le e \le s+M-2. \]

Now sweep \(s\) from left to right.

For each active endpoint \(e\) satisfying

\[ s \le e \le s+M-2, \]

it contributes the interval

\[ [e-B_e,\ e] \]

of possible split positions \(c\).

For the current start position \(s\), we need to count how many active intervals intersect

\[ [s-1,\ s+F_s-1]. \]

This can be done by maintaining all active intervals in a data structure that supports range add and range sum query.

Initially, insert the intervals for all endpoints \(e\) with \(0 \le e \le M-2\). When moving from \(s\) to \(s+1\), remove the interval for \(e=s\), and insert the interval for \(e=s+M-1\) if it exists.

Since \(c=s-1\) may appear, it is convenient to shift all indices by a constant in the implementation.

The required data structure supports adding \(+1\) or \(-1\) to an interval and querying the sum over an interval. This can be implemented with two Fenwick trees or a lazy segment tree.

If \(M=1\), there is no non-empty remaining substring after deleting a positive-length part, so the answer is \(0\).

The values \(F_s\) and \(B_e\) are computed in \({\cal O}(N+M)\) time using the Z-algorithm. During the sweep, each endpoint interval is inserted and removed at most once.

Therefore, the total time complexity is \({\cal O}((N+M)\log N)\).