Approach↵
==================↵
We will solve two parts separately. First lets find the min number of moves.<br>↵
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]`.<br>↵
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`.<br>↵
2. else for all `j`'s described above `ans[l][r] = min(ans[l][r], ans[l][j-1] + 1 + ans[j+m][r])` <br>↵
The minimum number of moves are `ans[0][n-1]`.<br>↵
Let call this answer `a1`.↵
<br>↵
<br>↵
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↵
1. 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.<br>↵
1.1. When we talk about deletion of index we only talk about last deleted index.↵
2. We try to make the string s, valid upto index i.↵
↵
<br>↵
`dp[i][j][0]` : No of vaild sequences upto index i, using j moves and not deleting index i.<br>↵
`dp[i][j][1]` : No of vaild sequences upto index i, using j moves and deleting index i.<br>↵
<br>↵
Observe that we will delete index `i` only if i belongs to validEnd.↵
↵
### Case 1 : i belongs to vaildEnd<br>↵
1. We can delete `s[i-m+1...i]` such that s upto index `i-m` has already been made valid.<br>↵
`dp[i][j][1] = dp[i-m][j-1][0] + dp[i-m][j-1][1]`.↵
2. 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 ways such that using `j` operations some index `k` such that`i-m+1 <= k < i` was deleted.↵
`dp[i][j][0] += dp[k][j][1]` for all `i-m+1 <= k < i`.<br><br>↵
↵
### Case 2 : i does not belong to vaildEnd<br>↵
we will never delete `i`, `dp[i][j][1] = 0,` and <br>↵
`dp[i][j][0] = dp[i-1][j][1] + dp[i-1][j][0]`↵
↵
Finally total number of valid sequences are `dp[n-1][a1][1] + dp[n-1][a1][0]`.↵
↵
[**CODE**](https://codeforces.net/contest/1729/submission/217967471)↵
==================↵
We will solve two parts separately. First lets find the min number of moves.<br>↵
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]`.<br>↵
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`.<br>↵
2. else for all `j`'s described above `ans[l][r] = min(ans[l][r], ans[l][j-1] + 1 + ans[j+m][r])` <br>↵
The minimum number of moves are `ans[0][n-1]`.<br>↵
Let call this answer `a1`.↵
<br>↵
<br>↵
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↵
1. 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.<br>↵
1.1. When we talk about deletion of index we only talk about last deleted index.↵
2. We try to make the string s, valid upto index i.↵
↵
<br>↵
`dp[i][j][0]` : No of vaild sequences upto index i, using j moves and not deleting index i.<br>↵
`dp[i][j][1]` : No of vaild sequences upto index i, using j moves and deleting index i.<br>↵
<br>↵
Observe that we will delete index `i` only if i belongs to validEnd.↵
↵
### Case 1 : i belongs to vaildEnd<br>↵
1. We can delete `s[i-m+1...i]` such that s upto index `i-m` has already been made valid.<br>↵
`dp[i][j][1] = dp[i-m][j-1][0] + dp[i-m][j-1][1]`.↵
2. 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 ways such that using `j` operations some index `k` such that`i-m+1 <= k < i` was deleted.↵
`dp[i][j][0] += dp[k][j][1]` for all `i-m+1 <= k < i`.<br><br>↵
↵
### Case 2 : i does not belong to vaildEnd<br>↵
we will never delete `i`, `dp[i][j][1] = 0,` and <br>↵
`dp[i][j][0] = dp[i-1][j][1] + dp[i-1][j][0]`↵
↵
Finally total number of valid sequences are `dp[n-1][a1][1] + dp[n-1][a1][0]`.↵
↵
[**CODE**](https://codeforces.net/contest/1729/submission/217967471)↵
