Approach
We will solve two parts separately. First lets find the min number of moves.
Let n be the size of s and m be the size of t.
Minimum number of moves.
Let ans[l][r] denote minimum number of moves to delete all occurrence of t in s[l]...s[r].
1. if there is no index j, in [l,r] such that j+m-1 < r and s[j...j+m-1] == t then ans[l][r] = 0.
2. else for all j's described above ans[l][r] = min(ans[l][r], ans[l][j-1] + 1 + ans[j+m][r])
The minimum number of moves are ans[0][n-1].
Let call this answer a1.
Number of ways to achieve those minimum number of ways.
Let's store all index j such that s[j-m+1....j] == t, in array validEnd.
Observations
- A move deletes a sub-array and we can only work with last deleted index of that sub-array, as last deleted index completely defines a move.
- We try to make the string s, valid upto index i.
dp[i][j][0] : No of vaild sequences upto index i, using j moves and not deleting index i.
dp[i][j][1] : No of vaild sequences upto index i, using j moves and deleting index i.
Observe that we will delete index i only if i belongs to validEnd.
Case 1 : i belongs to vaildEnd
We can delete s[i-m+1...i] such that s upto index i-m has already been made valid.
Or we will not delete i if some previous deletion already has made it impossible to pair s[i-m+1...i], which is just saying that total way dp[k][j][1], such that i-m+1 <= k < i.
