問題

文字列 $ s $ の異なるsubstringのうち辞書順で $ K $ 番目に小さいものを出力せよ。

出典

考えたこと

substringは連続するものであり場所が違っても文字列として同じなら同一視して複数とは数えない。 じゃあ、dict, set, map といったデータ構造を使えばいっか〜。

解法

提出 1 (TLE)

全ての部分文字列を抜き出してC++のmapに突っ込んで、最後にループで回して $ K $ 番目のキーを出力。

提出 2 (TLE)

計算量を落としたいと考えメモ化再帰。

string s;
map<string,int> cnt;
int flag[5050][5050];

void dfs(int i, int j) {
   if (flag[i][j]) return;
   else flag[i][j] = 1;
   string sub = s.substr(i,j-i);
   // まだ見てないなら分割
   if (cnt.find(sub) == cnt.end()) {
      cnt[sub]++;
      rng(l, i+1, j) {
         dfs(i,l);
         dfs(l,j);
      }
   }
}

flagで位置として訪れたかを管理するのはsubstringを取り出して訪れたかを確認する処理でも事足りるため少し冗長になった気もするがとにかく間に合わない。

提出 3 (WA)

ここにきて $ K $ が高々 $ 5 $ でしかないことに気づいた。だったら辞書順で列挙して $ K $ 個列挙した時点で終了すればええやん！

これはシンプルに再帰で実装したつもりがバグっていてWA。

提出 4 (AC)

バグを直してAC。

string s;
map<string,int> cnt;

void search(string h) {
   if (cnt.size() >= k) return;
   // 走査するprefixをkeyにもつ
   map<string,int> dict;
   int nh = h.size();
   rep(i,s.size()-nh) {
      bool same = true;
      rep(j,nh) {
         same = same && h[j] == s[i+j];
      }
      if (same) {
         dict[s.substr(i,nh+1)]++;
      }
   }
   for (auto [str,v] : dict) {
      cnt[str]++; // このタイミングでsubstringとして追加
      search(str);
   }
}

何を間違えていたかというとprefix文字列の列挙とその探索順序。幅優先探索や深さ優先探索で言われるin-orderなのかpost-orderなのかとかが判然としないけどタイミングが重要ということ。

公式解説

$ K $ が小さいので辞書順で $ K $ 番目の文字列の長さも高々 $ K $ 以下になるので長さ $ K $ 以下のsubstringを列挙するというとてもシンプルなもの。コンテストではこういう風に上手い落とし所をさっと見抜けるようになりたい。

まとめ

制約を考慮してsubstringを列挙すればいい問題ではあったが、ある順序に基づいて対象を列挙したいときに再帰（あるいは深さ優先探索）が使えることがわかった。