\(S[L,R)\) で \(S\) の \(L\) 文字目から \(R-1\) 文字目(0-indexed)を表します．

まず答えの桁数について考えます． \(K=1\) のとき，答えは明らかに \(\lceil \frac{N}{M}\rceil\) 桁です． \(K\geq 2\) のときは一つだけ \(N-M+1\) 桁にして残りを \(1\) 桁にすることができるので，答えは \(1\) 桁です．

\(K=1\) のとき

\(L=\lceil \frac{N}{M}\rceil\) とします．\(S\) を分割するとき，それぞれの文字列の長さは \(L\) または \(L-1\) に限定しても答えは変わらないことが示せます．

答えは \(S[0:L), S[1:L+1),\ldots\) のいずれかです．これらを Suffix Array 等を用いてあらかじめソートしておき，答えを二分探索をします．答えが \(X\) 以下か？という判定問題は，以下のような \(N+1\) 頂点の有向グラフにおいて頂点 \(0\) から \(N\) までの最短距離は \(M\) 以下か？という問題になります．

• 各 \(i=0,1,\ldots,N-L+1\) に対して， \(i\to i+(L-1)\) に辺を張る
• 各 \(i=0,1,\ldots,N-L\) に対して，もし \(S[i:i+L)\leq X\) なら \(i \to i+L\) に辺を張る

よってこの判定問題は \(O(N)\) で解けるので，もとの問題を \(O(N\log N)\) で解くことができます．

\(K\geq2\) のとき

答えが \(k\) 以下になるか？を \(1\) から \(9\) の順に試します． \(S\) に \(M-1\) 個の仕切りを入れて \(M\) 個の文字列に分割することを考えると， 「\(x\) 個の仕切りを新たに追加することで \(k\) 以下の整数が \(y\) 個作れる」という状態がいくつかできるので，あとは貪欲に仕切りを追加していけばよいです．計算量は文字の種類数を \(\sigma=9\) として \(O(N\sigma)\) や \(O(N\log \sigma)\) です．

実装例