Lexicographically Minimal String Rotation (Booth's Algorithm)
概要
何となく理解したので自分用のメモ
文字列 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[j]<S[k+i+1]) k = j-i-1; i=f[i]; } if (S[j]!=S[k+i+1]) { if (S[j]<S[k+i+1]) k = j; f[j-k] = -1; } else { f[j-k] = i + 1; } } return k; }
解説
表記
- s = 入力文字列
- s[i:j] = s[i] s[i+1] ... s[j]
- n = |s|
- S = s + s
- N = |S|
- 文字列の prefix と suffix はその文字列自身を含まない
- 「辞書順最小な suffix」における辞書順最小は，通常の辞書順最小と異なり文字列 A が文字列 B の suffix である場合 A > B とする
- すなわち aa における辞書順最小な suffix は a ではなく aa である
- （できたら呼び方変えたい）
j = j のループが終わったあとの各変数の意味
- k = S[:j] において辞書順最小なsuffix
- i = S[k:j] のprefixとsuffixが最大何文字一致しているか
- f[a] = S[k:k+a-1] においてprefixとsuffixが最大何文字一致しているか（failure link）
通常の KMP に k が加わったという感じになる
j のループが全て終わったあと
- k < n
- すぐ示せる
- S[k:k+n-1] が s のLMSR
- l < n, l != k のとき S[k:k+n-1] < S[l:l+n-1] を示せれば良い
- s[k:] < s[l:] を使って場合分けすれば示せる
