エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
競技プログラミング+αなブログ
概要 何となく理解したので自分用のメモ 文字列 s を cyclic に回転させた時の辞書順最小の文字列を求め... 概要 何となく理解したので自分用のメモ 文字列 s を cyclic に回転させた時の辞書順最小の文字列を求める問題をO(n)で解く 呼び方が色々ありそうだけど Wikipedia の Lexicographically Minimal String Rotation (以下 LMSR) を採用する LMSR は Suffix Array でも求められそうだけどこっちのほうが効率いいだろうし文字列アルゴリズムの勉強ということで コード int LMSR(const string &s) { string S = s + s; int N = S.size(); vector<int> f(N, -1); int k = 0; for (int j=1; j<N; ++j) { int i = f[j-k-1]; while(i!=-1 && S[j]!=S[k+i+1]) { if (S[