String DP

Dynamic programming where the state is a position (or a pair of positions) in one or more strings, or a state in an automaton built from a pattern.

The three shapes

1. Two-sequence DP — dp[i][j]

Position $i$ in $s$, position $j$ in $t$.

Problem	Recurrence
LCS	match $\to$ dp[i-1][j-1]+1, else max(dp[i-1][j], dp[i][j-1])
Edit distance	1 + min over insert / delete / replace
Longest common substring	match $\to$ dp[i-1][j-1]+1, else 0
Regex / wildcard matching	* branches into “consume” and “skip”
Interleaving check	dp[i][j] = can $s[\mathrm{0..}i)$ and $t[\mathrm{0..}j)$ interleave to form the prefix of $u$
Distinct subsequences count	dp[i][j] += dp[i-1][j-1] on a match
Shortest common supersequence	$n+m-\mathrm{LCS}$, then reconstruct

$O(nm)$, and $O(\min (n,m))$ space with a rolling array — or Hirschberg if you also need the alignment.

2. Interval DP — dp[l][r]

Problem	Recurrence
Longest palindromic subsequence	ends match $\to$ dp[l+1][r-1]+2, else max of peeling one end
Minimum insertions for a palindrome	$n-\mathrm{LPS}$, or a direct interval DP
Remove boxes / Zuma	needs a third dimension for “attached” elements
Count palindromic subsequences	inclusion-exclusion on the ends
Optimal string parenthesisation	split at $k$

See Interval DP.

3. Automaton DP — dp[i][state]

Build an automaton from the pattern(s), then do a DP over (length, automaton state). This is the shape for counting strings with constraints.

Automaton	Counts
KMP automaton	strings avoiding one pattern
Aho-Corasick	strings avoiding any of several patterns
Suffix automaton	distinct substrings, $k$-th substring
Trie	strings from a dictionary
Custom DFA	strings satisfying a regular property

// count strings of length L over an alphabet of size A avoiding the pattern
// aut[state][c] from the KMP automaton; state == m means "matched", forbidden
dp[0][0] = 1;
for (int i = 0; i < L; i++)
    for (int st = 0; st < m; st++)
        for (int c = 0; c < A; c++) {
            int ns = aut[st][c];
            if (ns == m) continue;                     // would complete the pattern
            dp[i+1][ns] = (dp[i+1][ns] + dp[i][st]) % MOD;
        }

When $L$ is huge ($10^{18}$), the transition is a fixed matrix — use matrix exponentiation over the $m\times m$ automaton, giving $O(m^3\log L)$.

That combination — Aho-Corasick automaton + matrix power — is the standard solution to “count length-$L$ strings containing none of these $k$ patterns”, and it is worth recognising on sight.

Common building blocks

Need	Precompute
”Is $s[l..r]$ a palindrome?” in $O(1)$	an $O(n^2)$ boolean table, or hashes
”Where does the next occurrence of $c$ start?”	nxt[i][c] — the next position $\ge i$ with character $c$
“Is $s[l..r]=t[l^{\prime }..r^{\prime }]$?“	hashing, or a suffix array + LCP
Longest common extension	LCP via sparse table over the LCP array

The nxt[i][c] table is underused: it turns “find the next matching character” from a scan into an $O(1)$ lookup, and it is exactly what makes subsequence-matching DPs and “$k$-th distinct subsequence” problems efficient.

vector<array<int,26>> nxt(n + 1);
nxt[n].fill(n);
for (int i = n - 1; i >= 0; i--) { nxt[i] = nxt[i+1]; nxt[i][s[i]-'a'] = i; }

Counting distinct subsequences

// number of distinct subsequences of s
vector<long long> dp(n + 1, 0);
dp[0] = 1;
vector<int> last(26, -1);
for (int i = 0; i < n; i++) {
    dp[i+1] = 2 * dp[i] % MOD;
    if (last[s[i]-'a'] != -1) dp[i+1] = (dp[i+1] - dp[last[s[i]-'a']] + MOD) % MOD;
    last[s[i]-'a'] = i;
}

The subtraction removes the subsequences double-counted because of a repeated character — a small inclusion-exclusion that is easy to get wrong and worth memorising.

See also: Dynamic Programming · Aho-Corasick · Strings