Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Let <code>dp[i]</code> be the minimum cost to form the prefix of length <code>i</code> of <code>target</code>.
Use Rabin-Karp to hash every prefix and store it in a HashSet.
Use Binary search to find the longest substring starting at index <code>i</code> (<code>target[i..j]</code>) that has a hash present in the HashSet.
Inverse Modulo precomputation can optimise hash calculation.
Use Lazy Segment Tree, or basic Segment Tree to update <code>dp[i..j]</code>.
Is it possible to use two TreeSets to update <code>dp[i..j]</code>?