Codeforces Round #635 div2-E (div1-C) Kaavi and Magic Spell 解説

問題リンク(div2)https://codeforces.com/contest/1337/problem/E

問題概要

2つの文字列$S,T$が与えられる。$S$を左から1文字ずつ取り出して別の場所に並べていく。$i+1$文字目を取り出すとき、$i$文字目まででできた列の先頭か最後尾に置くものとする。このとき接頭辞が$T$に一致する数を$998244353$で割った余りを求めよ。ただし、取り出している途中過程で接頭辞が$T$に一致するときも答えに含むものとする。また、前に置いても後ろに置いても同じ文字ができる場合は、それぞれ別のものとしてカウントすることにする。

制約 : $1≦|T|≦|S|≦3000$

例 : $S ="abab",\quad T="ba"$

最初、先頭と末尾どちらに追加してもできる文字は"a"となる(つまり2回カウント)。それから$S$の次の文字bを先頭に加えると"ba"(図の左), 最後尾に加えると"ab"(図の右側)のようになる。これを$S$が空になるまで繰り返す。このとき、途中経過含めて接頭辞が$T="ba"$に一致するのは赤く表示された6つである。ただし最初のaが先頭と最後尾どちらに追加されても同じ遷移をたどるので、最終的な答えは$6\times2=12$となる。

考察

以降 $ |S|=n,|T|=m $ とします。 $n≦3000$という制約と、1文字ずつ追加ということでdpを考えます。

$dp[i][j]$…$T$の左から$i$番目(以降全て0-indexed)から$j$個文字が一致している場合の数(添え字$j$を右端のindexとしても解けます)

dpテーブルの初期化

各iについて、i番目から0文字部分は$T$と一致すると考えられるので(イメージは少しつきにくいですが…)、初期化は $$ dp[i][0] = 1\quad(i=0,1,…n) $$となります。 ここで、$ i>m $を満たす$i$にもdp配列を定義することに注意します(遷移のところで後述します)

dp遷移

文字列$S$の$j$番目を見ているとき、並べられている数はぴったり$j$個なので、dp遷移の中で、配列の2つ目の添え字は必ず$j\rightarrow j+1$に移行します。文字列$S$を一回取り出すときに考えるべき遷移は、先頭に追加・最後尾に追加の2つです。説明の都合上最後尾の方から詰めていきます。

①最後尾に追加

このとき、左端の位置は変わらず、文字数だけが1増えることになります。
まず$ i+j<m $であるとき、つまり$T$の左端から$i$番目のところから$j$文字取り出しても右端に届かないときを考えます。 $dp[i][j+1] = dp[i][j+1] + dp[i][j]$となる条件は$S[j]=T[i+j]$、つまり追加しようとしている箇所の文字が$T$の該当箇所に一致することです。逆に$S[j]\neq T[i+j]$であるとき、これから右に追加しても$T$と一致する可能性が一切ないので、左端が決まっている以上棄却されることになります。
次に$ i+j≧m $のときを考えます。このとき、右端に追加するときにはすでに$T$の範囲から外れることになります。つまり何を追加しても条件を満たすことがわかります。よって必ず $$dp[i][j+1] = dp[i][j+1] + dp[i][j]$$となります。

②先頭に追加

このとき、①と同様に2つ目の添え字は$j\rightarrow j+1$となります。1つ目の添え字については、左端が一つ左にずれるので$i\rightarrow i-1$となります。 遷移は①の時と似たようなものになります。まず$ i=0 $のときは先頭にこれ以上追加できないので遷移はありません。次に$ i≦m $のとき、$S[j]=T[i-1]$なら先頭に追加できるので $$ dp[i-1][j+1] = dp[i-1][j+1] + dp[i][j]\quad if \quad i>0\quad and\quad S[j]=T[i-1] $$となります。 また、$ i>m $であるとき、先頭に何を追加しようと$ T $とは関わりを持たないので、必ず

$$ dp[i-1][j+1] = dp[i-1][j+1] + dp[i][j] $$が成り立ちます

以上の遷移をまとめると以下のようになります。 $$ dp[i][j+1] = dp[i][j+1] + dp[i][j]\quad if\quad i+j≧m\quad or\quad S[j]=T[i+j] $$$$ dp[i-1][j+1] = dp[i-1][j+1] + dp[i][j]\quad if\quad i>0\quad and \quad (i>m\quad or \quad S[j]=T[i-1]) $$

dpテーブルを埋めていく様子の一部を表すと次のようになります。(最初に書いた$S="abab",\quad T = "ba"$を例にします) $dp[0][0]\rightarrow dp[0][1]$については$S[0]\neq T[0]$なので加算されず、 $dp[1][0]\rightarrow dp[0][1]$についても$S[0]\neq T[0]$なので加算されません。

$dp[1][0]\rightarrow dp[1][1]$については$S[1]=T[1]=a$ なので加算されます。 $dp[2][0]\rightarrow dp[1][1]$についても$S[1]=T[1]=a$ なので加算されます。

$dp[1][1]\rightarrow dp[1][2]$については、$ m=2 $ なので $ i+j=2≧m $となり、最後尾に任意に追加できるので加算されます。 $dp[2][1]\rightarrow dp[1][2]$については$S[2]\neq T[1]$なので加算されません。

dpテーブルを埋めきると以下のようになります。 実装を単純化するために$ i+j≧n $となるときの遷移は無視しています(答えには影響しません)

答え

最後答えにする部分は、$T$の$0$文字目から$ m $字以上一致するものです($ m $字を超えるものについては、一致するというよりm字より先を無視できるという感じです) つまり

$ans = \sum_{j=m}^{n} dp[0][j] $

となります。