## Monday, October 13, 2014

### a bit of string dp: Codeforces Round #272 Problem E (Div. 2)

Problem Statement:
Codeforces - 476E

Summary:
Given a string $$s$$ and a pattern $$p$$. Denote $$S_k$$ as the set of strings produced from removing exactly $$k$$ letters from $$s$$. For each $$w \in S_k$$, we define occurrences of $$p$$ in $$w$$ as the maximum number of non-overlapping substrings of $$w$$ that match $$p$$ exactly. Then our task is, for each $$k \leq |s|$$ output the maximum occurrences of $$p$$ amongst all $$w \in S_k$$.
$$|s| \leq 2000, |p| \leq 500$$

Solution:
Firstly, suppose that we are considering the [i .. $$|s|$$] part of the string s. If we denote next[i] as the index immediately next to the end of a minimum length subsequence in [i .. $$|s|$$] that matches p. We also denote cost[i] as the number of letters that must be skipped (or deleted) in order to complete that subsequence. Then we have the following recursive relationship:
Denote L(i, k) be the maximum occurrences of pattern p in a substring [i .. $$|s|$$] after deleting exactly $$k$$ letters. Then
L(i, k) = max { L(i+1, k), L(next[i], k - cost[i]) }
Our answers would be on L(0, k) for all the required k values.