C++SA-ISを実装しようなという話です。SA)を線形時間で構築するアルゴリズムです。Wikipediaわざわざ言うほどのことじゃないのでこれ読んでください。長さSの文字列が与えられるのでSAを構築せよ。何も考えないでSAを求めるアルゴリズム長さが1~Sの文字列があると思ってソートを行います。程度なら実装も楽だしこの方法でよいです。algorithm)蟻本に詳しいことは書いてあるので持っている人はそちらを参考にしてください。ダブリングというテクニックを使います。簡単に言うと、先頭1文字でソートして、それを用いて先頭2文字でソートして、それを用いて先頭4文字でソートして・・というのを繰り返します。程度なら多分大丈夫です。いうか、多くの問題においてはこの方法で十分です。超頭のいいアルゴリズム(SA-IS)文字列をソートするのに線形時間しかかからないという頭のおかしいアルゴリズムです。有名なアルゴリズムなので解説記事がネット上にたくさん転がっていますが、僕がもっともわかりやすいと思ったのは以下の記事です。アルゴリズムを理解したいなら以下の記事を繰り返し読むといいと思います。bucketなどの意味は上記のサイトを読んでください。アルゴリズムの内容も上記のサイトを読んでください()。sortを実行するとLMS-substringがソートされるということです。実際に手を動かしてみれば証明するのは簡単です。SA-ISの実装の流れ(あくまで僕の実装)アルゴリズムを理解しても実装の流れがつかみにくいということがあると思う(僕はそうだった)ので、僕の実装の流れを書きます。これはあくまで僕の実装なのでもっとよい実装はいくらでもあることに注意してください。char型だと後々扱いにくいのでint型に変換する。sortを実行する先頭にあるダミー値を削除する得られた数列を返すこうしてみるとどれも簡単なものばかりで楽そうなのですが、僕の場合は0-indexedと1-indexedが混ざったり、7の処理を抜かしていてバグらせまくったりしました。おわりに実はSA-ISを使う問題に実際に出会ったことはないのですが、イマドキの人はSA-ISは持っているものという認識が広まりつつあるので実装しました。して見ると言うほど複雑ではないので実装してみるといいと思います(hogehuga木のpiyoとかのほうが全然難しそう)。一応僕の実装を載せておきますが、とりあえず線形時間でSAを求めたというだけで定数倍が非常に重いですし、無駄な処理も多いのであまり参考にしないほうがよいです(ただ、一応上記の方針の通りに実装しています)。ライブラリ化したいならvectorにこんな頻繁にpush_backしてはいけませんし、もっと洗練させたほうがいいです(僕は今はそのモチベーションがないのでとりあえずこれで)。検索はてなブログをはじめよう!gasinさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。