kaage精進録

雑な解説とかライブラリとかおきもちの垂れ流しです。

2008JOI本選2 共通部分文字列解説

JOI 解説

問題リンク

解説

この問題は、LCS（Longest Common Substring）という有名問題です。具体的には、次のような動的計画法（DP）をします。

$dp\left[i\right]\left[j\right]$ を、「一つ目の文字列で $i$ 文字目、二つ目で $j$ 文字目まででのLCSの最大の長さ」とします。このとき、遷移式は次のようになります。

$s\left[i\right]=s\left[j\right]$ のとき、 $dp\left[i\right]\left[j\right]$ から $dp\left[i+1\right]\left[j+1\right]$ へ、1増やして遷移する
そうでない場合、 $dp\left[i\right]\left[j\right]$ から $dp\left[i+1\right]\left[j\right],dp\left[i\right]\left[j+1\right]$ へ、数を変えずに遷移する

それぞれの遷移では、遷移先が最大値を取るように、遷移先とのmaxを代入する必要があります。

このようなDPの問題では、問題の制約を見てDPが使えることに気づき、使える場合、どのようなDPをすればいいかに慣れることが大事です。

この程度の難易度のDPの問題はJOIの過去問にたくさんありますので、積極的に解いて、DPの式を立てる作業に慣れましょう。制約をよく見ることも大事です。