2026-10-18
with_prefix.cpp
#include <string>
#include <string_view>
#include <vector>
std::vector<std::string> with_prefix(const std::vector<std::string>& words, std::string_view p) {
}
辞書式の昇順に並んだ words から、文字列 p で始まる単語をすべて、words での順のまま返す with_prefix を書いてください。p で始まる単語が無ければ空の vector を返し、p が空文字列ならすべての単語を返します。words の要素数を n として、単語どうしの比較は O(log n) 回に収めます。
入力例 1
with_prefix({"car", "cart", "cat", "dog"}, "car")
出力例 1
{"car", "cart"}
入力例 2
with_prefix({"car", "cart", "cat", "dog"}, "ca")
出力例 2
{"car", "cart", "cat"}
入力例 3
with_prefix({"car", "cart", "cat", "dog"}, "x")
出力例 3
{}
Reference
#include <algorithm>
#include <string>
#include <string_view>
#include <vector>
std::vector<std::string> with_prefix(const std::vector<std::string>& words, std::string_view p) {
auto head = [&](std::string_view w) { return w.substr(0, p.size()); };
auto [lo, hi] = std::ranges::equal_range(words, p, {}, head);
return std::vector<std::string>(lo, hi);
}
辞書式の順では、p で始まる単語は1か所に続けて並びます。どの単語も先頭の p.size() 文字に切り詰めて見ると、並びの順は崩れず、切り詰めた値が p と等しい単語がちょうど求める範囲になります。そこで、切り詰めた値で比べる equal_range を使い、等しい値の範囲として始まりと終わりを一度に求めます。
std::ranges::equal_range の4つ目の引数 head は射影(projection)で、比べる前に要素へ適用されます。射影が掛かるのは要素の側だけで、探す値の p はそのまま比べられます。string_view::substr は残りの長さが足りなければ末尾までを返すので、p より短い単語もそのまま比べられます。
始まりは lower_bound(p) でも求まりますが、終わりに upper_bound(p) を使うと範囲が足りなくなります。単語全体と比べる限り、p と等しい単語は p そのものだけで、upper_bound はそれより大きい最初の単語を指すからです。"cart" は "car" より大きいので、p が "car" のときの範囲は "car" だけで終わります。
掲載したのは参考実装で、唯一の正解ではありません。終わりの位置は、p の最後の文字を1つ大きくした文字列を lower_bound で探しても求まりますが、最後の文字が char の最大値のときは別の扱いが要ります。