弊社はエンジニアを熱烈募集しています． 以下から気軽にカジュアル面談申し込んでください． 就職・転職を考えている知人にも積極的に宣伝してください．
Spir | Smart scheduling calendar
この勉強会の宣伝もお願いします． 参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会 で実況や感想，質問を呟くなども．
以下のリンクから匿名発言が出来るはずです． 質問だけじゃなく実況なども気軽にしてください．
Join Slido: Enter #code to vote and ask questions
部屋番号 3278275 部屋名 : #12
文字の種類数を $\sigma$ で表すことにする． 例えば英小文字を扱う時は $\sigma=26$．
以下では $\sigma$ はあまり大きくないことを想定（競プロだと $26$ のことが多い）． これが $\sigma=10^9$ などの場合は実装を一部変更する必要がある．
文字列を $s,t$ などの英小文字で表し，文字列集合を $S,T$ などの大文字で表す． 文字列 $s$ の長さを $|s|$ で表記する．（例: $s=\text{”abca”}$ の時 $|s| = 4$ ）
文字列集合 $S$ を管理するデータ構造． 初め $S$ は空として，以下のクエリが処理出来る．
add(s) $S$ に文字列 $s$ を追加 : $\Theta(\sigma|s|)$ 時間is_exist(s) $S$ に文字列 $s$ が存在するかを判定 : $\Theta(|s|)$ 時間他にも（ std::set では扱えない）色々なクエリが処理できる（後述）
空間計算量は $\Theta(\sigma\sum_{s\in S} |s|)$