この解説中で、文字列 \(s\) の \(l\) 文字目から \(r\) 文字目を抜き出した文字列を \(s[l,r]\) と書きます。

\(S\) に K, U, P, C のうち含まれない文字があれば、答えは -1 です。以降、このケースを除去して考えます。

\(S\) を無限回繰り返した文字列を \(S^{\infty}\) とします。
文字列 \(T\) に対し、次の条件を満たす最小の \(x\) を \(f(T)\) と定義します。

• \(S^{\infty}[1,x]\) に、 \(T\) が (連続でなくともよい) 部分列として含まれる。

\(U\) の要素 \(T\) であって、 \(f(T)\) が最大となるものを考えましょう。そのような \(T\) が求まれば、求めるべき最小の \(k\) は \(\lceil f(T)/|S| \rceil\) となります。
これは、次の貪欲法により求まります。

• 最初、 \(r=0\) から始める。
• 以下の手順を \(L\) 回繰り返す。
  • \(S^{\infty}\) の \(r+1\) 文字目以降のみに着目した際、 K, U, P, C のうち最後に現れる文字の位置を新たな \(r\) とする。
• 繰り返しが終わった時点での \(r\) が \(f(T)\) である。

この問題では \(L \le 10^{18}\) なので、これを愚直に実行することはできません。どのように計算量を改善すれば良いでしょうか?

まず、次の事実を利用します。

• K, U, P, C のうち最後に現れる文字の位置を考える際、 \(S^{\infty}\) の \(r+1\) 文字目以降を考えることと \(S^2\) の \((r\%|S|)+1\) 文字目以降を考えることとは等価である。 ( \(a \% b\) で \(a\) を \(b\) で割った余り )
• \(S^2\) において、 K, U, P, C のうち最後に現れる文字の位置は \(O(|S|)\) で予計算できる。

これを利用すると、 \(L\) 回の繰り返しは ダブリング により高速に行うことができます。 ダブリングの解説自体は この問題の解説 等に譲ります。

今回は次の情報を保持してダブリングを行うべきです。

• 各 \(1 \le r \le |S|\) について、 \(r\) から始めて \(2^t\) 回の繰り返しを行った時、 \(f(T)\) はいくつ増加するか?

実装上は、 \(f(T)\) の代わりに「 \(S\) を追加で \(x\) 周した後、次の \(r \% |S|\) が \(y\) となる」といった情報を保持すると良いです。( \(f(T)\) を保持すると必要になる多倍長整数を使わずに済みます )