## Intuition The problem requires us to find the number of ways to extract `k ≥ 1` non-overlapping substrings from a given string `s` such that each substring contains another string `t` as a substring. The key insight is to recognize that this problem can be solved using dynamic programming by leveraging the positions where `t` occurs in `s`. ## Approach 1. **Preprocessing with KMP Algorithm**: First, we need to find all occurrences of `t` in `s`. This can be efficiently done using the Knuth-Morris-Pratt (KMP) algorithm, which allows us to find all starting indices of `t` in `s` in linear time. 2. **Dynamic Programming Setup**: Define a DP array `dp[i]` where `dp[i]` represents the number of ways to choose non-overlapping substrings ending at or before position `i` such that each contains `t` as a substring. 3. **Transition**: For each position `i` in `s` where `t` ends, update the DP array. If `t` ends at position `i`, then for each `j` where `t` starts (i.e., `j = i - |t| + 1`), add to `dp[i]` the number of ways to form valid substrings up to `j-1`. This ensures non-overlapping condition. 4. **Prefix Sum Optimization**: To efficiently compute the sum of `dp` values up to a certain point, maintain a prefix sum array `sum[i]` where `sum[i]` is the sum of `dp` values up to `i`. 5. **Final Computation**: The result is the sum of `dp[i]` for all `i` where `t` ends in `s`. 6. **Modulo Operation**: Since the number of ways can be large, use modulo `10^9 + 7` for all operations to prevent overflow. ## Complexity - **Time Complexity**: O(n + m), where `n` is the length of `s` and `m` is the length of `t`. This is due to the KMP algorithm and the linear scan for DP updates. - **Space Complexity**: O(n), for storing the DP and prefix sum arrays. ## Solution (C++) ```cpp #include using namespace std; const int MOD = 1e9 + 7; vector kmp(const string& pattern, const string& text) { int m = pattern.size(); int n = text.size(); vector lps(m, 0), result; // Preprocess the pattern to create the lps array for (int i = 1, len = 0; i < m;) { if (pattern[i] == pattern[len]) { lps[i++] = ++len; } else if (len) { len = lps[len - 1]; } else { lps[i++] = 0; } } // Use the lps array to find matches for (int i = 0, j = 0; i < n;) { if (pattern[j] == text[i]) { i++; j++; } if (j == m) { result.push_back(i - j); j = lps[j - 1]; } else if (i < n && pattern[j] != text[i]) { if (j) j = lps[j - 1]; else i++; } } return result; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s, t; cin >> s >> t; int n = s.size(), m = t.size(); vector occurrences = kmp(t, s); vector dp(n + 1, 0), sum(n + 1, 0); dp[0] = 1; // Base case: one way to choose no substrings sum[0] = 1; int occIdx = 0; for (int i = 1; i <= n; ++i) { dp[i] = dp[i - 1]; if (occIdx < occurrences.size() && occurrences[occIdx] + m == i) { dp[i] = (dp[i] + sum[occurrences[occIdx]]) % MOD; occIdx++; } sum[i] = (sum[i - 1] + dp[i]) % MOD; } cout << (sum[n] - 1 + MOD) % MOD << "\n"; // Subtract 1 to exclude the empty choice return 0; } ``` This solution efficiently computes the number of ways to extract the required substrings using dynamic programming and the KMP algorithm for pattern matching.

Obsessive String

Problem Details