NimK (index-K Nim) の必勝判定・必勝側の具体的な手の選択
- NimKの必勝判定
- 必勝側の具体的な手の選択
について書きます。
後者は前者の証明に出てくるのですが念のために?指す手を求めるプログラムを書きました。
必勝判定
NimK または index-K Nim とは通常の $N$ 山 Nim の変形で、各手番では山を $K$ 個まで選択して石をとることができるゲームです。それぞれの山に積まれている石の個数を $A_1, A_2, \dots, A_N$ 個とします。このゲームでは $A_i$ を $2$ 進表示したとき桁ごとにとった和について
- 和が $K+1$ の倍数でない桁があれば先手必勝
- すべて $K+1$ の倍数ならば後手必勝
が成り立ちます。
たとえば $N = 5, K = 3$ で石の個数が $(22, 11, 42, 23, 19)$ の局面を考えます。$2$ 進表示して各桁の和を $\mathrm{mod}\ K+1$ で求めると次のようになるためこの局面は先手必勝です。
010110 001011 101010 010111 010011 ------ 132113
証明: 次を示せばいいです。
先手必勝 → 後手必勝の手が存在する
後手必勝 → 後手必勝の手が存在しない (先手必勝に移る手しかない)
【$\exists$ 先手必勝→後手必勝】
$(A_1, \dots, A_N)$ が先手必勝だとします。また $S_i\ (i = 0, 1, \dots)$ を次のようにおきます。
- $A_1, \dots, A_N$ を $2$ 進表示して $2^i$ の桁について $\mathrm{mod}\ K+1$ で和をとった結果*1
示すべきことは $\forall i = 0, 1, \dots$ に対し $S'_i = 0$ となる $(A_1', \dots, A_N')$ が存在することです。ただし
- $A_j' \le A_j$
- $A_j' < A_j$ となる $j$ は最大でも $K$ 個
でないといけません。
$S_i$ が $0$ でない最大の $i$ を $t$ とします*2。$A_1, \dots, A_N$ のうちで $2^t$ の桁が $1$ になっているものが少なくとも $S_t$ 個あるので、それらを操作対象の山として選択します。選んだ山から石を $2^t$ 個ずつとると $S_t' = 0$ になります。そして、それぞれの石の個数について $2^{t-1}, \dots, 2^0$ の桁を $1$ にします*3。
次に $S_{t-1}'$ を見ます。$S_{t-1}' = 0$ ならば文句なしですが、そうでない場合でも $S_{t-1}' \le $ さっき選んだ山の個数 であれば問題ありません。実際、選んだ山に残っている石の個数について $2^{t-1}$ の桁を $1 \to 0$ にすることを $S_{t-1}'$ 回行えば $S_{t - 1}' = 0$ とできます。
$S_{t-1}' > $ さっき選んだ山の個数 であればしかたがないので必要な分だけ操作対象の山を増やすほかありません*4。さっき選んだ山といま選んだ山について、石の個数を以前のステップと同じように変化させます。つまり $2^{t-1}$ の桁を $1 \to 0$ にしてそれより下位の桁をすべて $1$ にします。
$S_{t - 1}' = 0$ にできたので、次は $S_{t - 2}'$ を見て...を $S_0'$ まで繰り返せばすべての $S_i'$ を $0$ にできるため、後手必勝の局面に移れることになります。
【$\not\exists$ 後手必勝→先手必勝】
$(A_1, \dots, A_N)$ が後手必勝だとします。簡単のため先頭から $k$ 個の山 $1, \dots, k$ を選んだとして、それぞれの山から $1$ つ以上石をとり $(A_1', \dots, A_k', A_{k+1}, \dots, A_N)$ になったとします。ただし $k \le K$ です。
各 $A_i'$ には $A_i' < A_i$ より $A_i$ では $1$ だった桁が $0$ になった箇所があります。$2^{r_i}$ に対応する桁がそのような桁のうちで最上位だとします。
$2^r := \max_{i}(2^{r_i})$ とおくと $2^r$ に対応する桁が $1 \to 0$ となった $A_i$ の個数は $1$ 以上 $k$ 以下です。一方 $0 \to 1$ となった $A_i$ は存在しないことが分かります。
$(A_1, \dots, A_N)$ に対し $2^r$ の桁について $\mathrm{mod}\ K + 1$ で和をとった値を $S_r$ として、$(A_1', \dots, A_k', A_{k+1}, \dots, A_N)$ に対するそれを $S_r'$ とします。$(A_1, \dots, A_N)$ は後手必勝だったので $S_r = 0$ であり、$S_r - k \le S_r' \le S_r - 1$ より $S_r'$ は $K+1$ で割り切れません。
したがって後手必勝の局面に移れません。
手の選択
先手必勝局面が与えられたとき、そこから移れる後手必勝局面を上の証明で出てきた手続きによって求めるプログラムです。計算量は $O(N(\mathrm{log}_2(\mathrm{max}A_i))^2)$ です。
#include <algorithm> #include <bitset> #include <cassert> #include <iomanip> #include <iostream> #include <vector> #define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; void print_vector(vector<int> &a) { for (auto e : a) { cout << setw(2) << e << " " << bitset<8>(e) << endl; } } int main() { int n = 5, k = 3; vector<int> a = {22, 11, 42, 23, 19}; puts("before:"); print_vector(a); vector<int> x; rep(i, 31) { int s = 0; for (auto e : a) { s += e >> i & 1; } x.push_back(s % (k + 1)); } assert(any_of(x.begin(), x.end(), [](const auto &e) { return e > 0; })); vector<int> chosen; for (int p = 30; p >= 0; p--) { for (auto j : chosen) { if (x[p] > 0) { a[j] ^= 1 << p; x[p]--; } } for (int j = 0; j < n and x[p] > 0; j++) { if (a[j] >> p & 1) { chosen.push_back(j); a[j] ^= 1 << p; x[p]--; for (int q = p - 1; q >= 0; q--) { if (!(a[j] >> q & 1)) { a[j] ^= 1 << q; x[q] = (x[q] + 1) % (k + 1); } } } } } puts("after:"); print_vector(a); assert(chosen.size() <= k); rep(i, 31) { int s = 0; for (auto e : a) { s += e >> i & 1; } assert(s % (k + 1) == 0); } return 0; }
実行すると次のような出力が得られます。
山 $2$ から石を $4$ 個とって山 $3$ から石を $21$ 個とったことが分かります。
before: 22 00010110 11 00001011 42 00101010 23 00010111 19 00010011 after: 22 00010110 7 00000111 21 00010101 23 00010111 19 00010011
まとめ
NimK では $N$ 個の山に積まれている石の個数を $2$ 進表示して各桁ごとに $\pmod{K + 1}$ で和をとった数を $X$ とすると
- $X$ (の $2$ 進表示) に $0$ でない桁があれば先手必勝
- すべての桁が $0$ ならば後手必勝
となります。必勝側のプレイヤーは $X$ の上位桁から見ていき各桁が $0 \pmod{K + 1}$ になるように各山の石を減らしていけばいいです。このとき、すべての桁を $0$ にするために触る山は最大でも $K$ 個で済みます。
参考
木の中心が直径上に存在すること・中心を見つけるアルゴリズム
- 木の中心が直径上に存在すること
- 中心を見つけるアルゴリズム
について書きます。
木の中心とは「各頂点への距離の最大値」が最小になる頂点 (の集合) です。
頂点 $v$ から各頂点への距離の最大値を $ E(v) $ と書きます。つまり、
$$ E(v) = \max_u\{\mathrm{dist}(v, u)\} $$
です。
頂点間の距離はそれらの間にある辺の本数です。
そして $E(v) = \min_u\{E(u)\}$ であるとき、頂点 $v$ は木の中心であるといいます。
言葉の感じから、中心は木の直径 (を与える $2$ 頂点を結ぶパス) の真ん中あたりにありそうな気がしてきます。
実際そうです。
$x, y$ を最遠点対とします。つまり、$d = \mathrm{dist}(x, y)$ は直径 $\max_{u}\{E(u)\}$ に等しいとします。
このとき、$x$ から $y$ の方向へ $\lfloor d/2 \rfloor$ 進んだ頂点を $c$ とすると $c$ は中心で $E(c) = \lceil d/2 \rceil = \mathrm{dist}(c, y)$ です。
任意に頂点 $v \neq c$ をとって $E(c) \le E(v)$ を示します。
そのためには、ある一つの $u$ に対して $E(c) \le \mathrm{dist}(v, u)$ が言えれば十分です。右辺は $E(v)$ 以下だからです。
さて、$v-x$ パスおよび $v-y$ パスを考えると、どちらかのパス上に $c$ があります。
- $v-c-x$ となっている場合、$\mathrm{dist}(v, c) \ge 1$ より $\mathrm{dist}(v, x) \ge 1 + \mathrm{dist}(c, x) = 1 + \lfloor d/2 \rfloor \ge\lceil d/2 \rceil = E(c) $
- $v-c-y$ となっている場合、$\mathrm{dist}(*, *) \ge 0$ より $\mathrm{dist}(v, y) = \mathrm{dist}(v, c) + \mathrm{dist}(c, y) \ge \mathrm{dist}(c, y) = E(c) $
$E(c) \le E(v)$ が言えたので $c$ は中心です。
また、$d$ が奇数のとき、つまり $\lfloor d/2 \rfloor \ne \lceil d/2 \rceil$ のとき $c$ から $y$ 側に $1$ 進んだ頂点もまた中心です。
証明は上の議論を $x$ と $y$ をひっくり返してコピペすればいいです (たぶん) 。
中心は直径上に存在し、その個数は $1$ つか $2$ つであることが分かりました。
それでは、$3$ つ以上存在しないことを示しましょう。
木の頂点数が $2$ 以下の場合はあきらかなので頂点が $3$ つ以上あるとします。
このとき、葉をぜんぶ取り去ったあとに残る木において、中心はもとの木の中心と一致します。
小さくなった木の任意の頂点 $v$ について $E(v)$ はもとの木でのそれより $1$ 小さいからです。
$E(v) = \max_u\{...\}$ を達成する $u$ は葉じゃないとおかしいですもんね。
残された木がまだ $3$ つ以上の頂点を持っていたら、葉を取り除く操作を繰り返します。
頂点が $2$ つ以下になっていたらそれら ($1$ つ or $2$ つ) が中心です。
ありがたいことに、この証明は具体的に中心の見つけ方を教えてくれています！
半径 $\min_u\{E(u)\}$ が欲しいだけなら、はじめにやったように直径を $2$ で割って切り上げするのが早いと思います。
直径は dfs を $2$ 回するアレで求まります。
この方法なら、終わったあとに直径の両端が手に入っているはずなので、パスをたどって中心を見つけてもいいです。
葉を削除していって中心を求めるアルゴリズムの実装例 (C++) を以下に示します。
直径を求める問題でむりやり使ってみるとこうなります：提出
#include <queue> #include <vector> using namespace std; vector<int> centers(const vector<vector<int>> &g) { int n = g.size(); vector<int> deg(n, 0); for (int i = 0; i < n; i++) { for (auto j : g[i]) { deg[j] += 1; } } queue<int> leaves; for (int i = 0; i < n; i++) { if (deg[i] == 1) leaves.push(i); } vector<int> removed(n, false); int remaining = n; while (remaining > 2) { queue<int> nxt; while (leaves.size() > 0) { auto leaf = leaves.front(); leaves.pop(); removed[leaf] = true; remaining -= 1; for (auto j : g[leaf]) { deg[j] -= 1; if (deg[j] == 1) nxt.push(j); } } leaves.swap(nxt); } vector<int> ret; for (int i = 0; i < n; i++) { if (not removed[i]) ret.push_back(i); } return ret; }
最後の仕事です。
上で「葉を取り除く操作を繰り返す」と言いましたが、葉はつねに存在するんですか？という質問に答えないといけません。
頂点数を $n \ge 3 $ とします。
木には葉が $2$ つ以上存在する
葉の個数を $k$ とおく。辺数は $n - 1$ だから次数の和について
$$\displaystyle k + \sum_{\mathrm{deg}(v) \ge 2} \mathrm{deg}(v) = 2 (n-1)$$
が成り立つ。シグマは葉以外の頂点 $n - k$ 個に対して和をとっている。したがって、上の式より $k + 2(n - k) \le 2(n - 1)$ だから $k \ge 2$ である。
参考
Every tree has either one or two center | Tutorials on Mathematics
KMP法
テキスト文字列 txt にパターン文字列 pat が現れる位置を求めます。
たとえば txt = "abaaaba", pat = "aab" のとき、テキストの $4$ 文字目からパターンが現れます。
abaaaba aab
素朴な方法として、パターンの開始位置を全通り試すというものがあります。
上と同じ例でテキストの $i$ 文字目 ($i = 1, 2, 3, 4$) とパターンの先頭を揃え、テキストの文字と異なる文字が現れるまでパターンを読んでいくと次のようになります。
x は初めてテキストの文字とパターンの文字が異なった位置を示しています。
abaaaba ax x aax aab
一般に、テキストの長さを $N$、パターンの長さを $ M $ とすると、素朴な探索法では文字の比較回数が最悪で $NM$ 回ほどになりえます。
具体的には txt = "aaaaaaaaaaaaaab", pat = "aaaaab" のようなケースが該当します。
パターンとの照合をテキストの $1$ 文字目から始めると $5$ 文字目までは互いの文字が一致しているので、リーチの状況まで持っていけます。
aaaaaaaaaaaaaab aaaaa_
あと $1$ 文字一致すれば晴れてテキスト内のパターン出現位置が特定できることになりますが、現実は非情でパターンの $6$ 文字目 (_ に入る文字) は b、テキストの $6$ 文字目は a なので異なる文字です。
テキストの $1$ 文字目から始まる文字列はパターンに一致しないことが分かりました。
そこで次はテキストの $2$ 文字目から始めて、パターンの先頭から $1$ 文字ずつ比較していきましょう。
しかしこの場合も先ほどと同様にリーチまではたどり着くものの、最後の $1$ 文字というところで不一致になってしまいます。
この繰り返しが $N - M + 1$ 回起こるため全体で $ (N - M + 1)M $ 回ほど文字の比較を行うことになります。
ふつう、テキストはパターンより十分長いため $NM$ に対して $M^2$ は無視できるほど小さいです。
したがって、素朴な方法の場合、特定のケースでは約 $NM$ 回の比較が必要になることが分かりました。
KMP 法はこのようなケースも含めて、文字の比較回数を最悪で $ N + M $ 回程度に抑えます。
上の方法では、テキストの文字とパターンの文字が不一致になったとき、それまで一致してきた文字数に関係なく一律でカーソル (テキストやパターンの見ている位置) をリセットしていました。
一致した文字数が少ない場合は、まあ仕方ないかと思えますが、たくさん一致していた場合はどこかもったいない気がしてきます。
実は、テキストのカーソルを戻すことなく、パターンの出現位置を検出することができます (パターンのカーソルはいくらか戻ります) 。
txt = "abababaabba", pat = "ababaabb" とします。
テキストの $1$ 文字目から照合を始めると、$6$ 文字目で初めて不一致が起こります。
v
abababaabba
ababax
^
このとき、カーソルはテキスト・パターンともに $6$ 文字目を指しています。
ここでテキストのカーソルを $2$ 文字目に、パターンのカーソルを $1$ 文字目に戻すのが素朴な探索法でした。
v ababababba _ ^
テキストのカーソルを動かさずに、パターンのカーソルのみを戻すことで照合を再開したいです。
$1$ 文字分だけカーソルを戻してみましょう。
カーソルは固定されていて、パターンの文字列全体を右に $1$ 文字分ずらすと考えてもいいです。
v
ababababba
abab_
^
_ はその文字をまだ見ていない (見る直前である) ことを示しています。
カーソルが指す文字同士を比較する以前に、この照合は失敗することが分かります。
なぜなら、長さ (文字数) $n$ の文字列同士が一致することは、先頭 $n - 1$ 文字が一致してさらに $n$ 文字目も同じ文字であることと同等だからです。
いまの場合、_ より左の $4$ 文字すべてがテキストの対応する位置にある文字と一致している必要がありますが、そうなっていません。
それでは、パターンのカーソルを $2$ 文字分戻してみましょう。
v
ababababba
aba_
^
幸運なことに、パターンの先頭から $3$ 文字 (_ までは達しない長さ) がテキストと一致しています。
したがって、照合はパターンの $4$ 文字目から始めればいいです。
$4$ 文字目が同じ文字なら次の文字 ($5$ 文字目) を比較し、そうでないならさらにパターンのカーソルを戻します。
このようにすれば、テキストのカーソルを動かすことなくテキストとパターンの照合を行うことができます。
上の例 (txt = "ababababba", pat = "ababaabb") では $6$ 文字目で不一致が起こった際に、パターンのカーソルを $2$ 文字分戻す必要がありました。
そうすることで、カーソル位置の直前までの (カーソルが指す文字を含まない) 文字列と、対応する位置にあるテキストの文字列が一致するのでした。
このようなカーソルの位置を見つけるにはどうしたらいいのでしょうか。
確実な方法は、例で行ったようにカーソルを $1$ つずつずらしていき、そのたびに条件を満たすかチェックするというものです。
しかし文字列同士の一致を判定するには、文字列の長さと同じ回数だけ文字を比較しなければいけません。
すると結局は、最悪の場合に全体で $NM$ 回程度の比較が必要になり、本末転倒感があります。
この問題を回避するために、パターンのカーソルが移動すべき位置について整理しましょう。
やはり上の例で $6$ 文字目に不一致が見つかった時点を考えます。
パターンのカーソルを $2$ 文字分戻すことは、パターン自身を右に $2$ 文字分ずらすことと同じでしたから次のようになります。
テキストの $6$ 文字目以降は気にしなくていいので省略しています。
ababa ababa
ここで "aba" が "ababa"(パターンの先頭から $5$ 文字を切り出した文字列) の prefix*1 であり suffix*2 でもあることに気づくかと思います。
この特徴は $1$ 文字ずらしのときには現れていません。
ababa ababa
"ababa" の prefix であり suffix でもあるような文字列で、長さが $4$ のものは存在しないからです。
したがって、カーソルの移動先を知るには $ j = 1, 2, \dots, M $ について
$\mathrm{next}[j] := $「パターンの先頭 $j$ 文字を切り出した文字列」の prefix であり suffix でもある文字列の最大長 (文字数)
が分かっていればいいです (ただし、prefix および suffix として文字列全体を取るのは禁止です) 。
実際、文字の不一致が起こったときに、パターンのカーソルが 0-indexed で $j$ 番目の文字を指していたとすると、次のカーソル位置として $\mathrm{next}[j]$ を選べます。
このときテキストのカーソルが $i$ 番目の文字を指していたとすると、テキスト上の $i$ の左隣り $\mathrm{next}[j]$ 文字は $\mathrm{next}[j]$ の定義より、パターン上の $\mathrm{next}[j]$ の左隣り $\mathrm{next}[j]$ 文字と一致しています。
よって $\mathrm{next}[j]$ はカーソルの移動先として適切です。
pat = "ababaabb" に対する $\mathrm{next}[]$ 配列を以下の表に示します。
| j | next[j] | パターンの先頭 j 文字 |
|---|---|---|
| 0 | -1 | |
| 1 | 0 | a |
| 2 | 0 | ab |
| 3 | 1 | aba |
| 4 | 2 | abab |
| 5 | 3 | ababa |
| 6 | 1 | ababaa |
| 7 | 2 | ababaab |
| 8 | 0 | ababaabb |
実装の都合上 $\mathrm{next}[j] = -1$ としておくといいです。
テキスト文字列 txt とパターン文字列 pat を受け取って、テキスト内にパターンが最初に現れる位置 (存在しなければ $-1$) を返す関数 kmp_search は次のように実装できます。
int kmp_search(const string &txt, const string &pat) { vector<int> next = build_next(pat); int i = 0, j = 0; while (i < txt.size() and j < pat.size()) { while (j >= 0 and txt[i] != pat[j]) { j = next[j]; } i += 1; j += 1; } if (j == pat.size()) { return i - j; } else { return -1; } }
内側の while を抜けた直後は j == -1 または txt[i] == pat[j] です。
後者は分かりやすいと思います。
パターンの先頭 $j$ 文字の照合が完了していて、0-indexed で $j + 1$ 番目の文字も一致した (txt[i] == pat[j]) という状況です。
次の文字を比較するためにテキストのカーソルとパターンのカーソルを $1$ つずつ進めます (i += 1; j += 1;) 。
前者について考えます。
while 内部の j = next[j]; はパターンのカーソルを左に動かす処理でした。
しかし、カーソルを戻せる範囲にも限界があります。
具体的にはパターンの先頭まで、つまり $j = 0$ までです。
先頭まで戻ってきて pat[0] とテキストのカーソルが指している文字 txt[i] を比較しますが、これすら異なっていたらもはやできることはありません。
次の比較では txt[i + 1] と pat[0] をチェックしたいです。こちらならまだ可能性があります。
while のあとにインクリメントされることを考えると、$i$ はそのままにしておき、$j$ には $-1$ をセットすべきです。
ちょうど next[0] には意味のある値は入っていません。
ここに $-1$ を格納しておけば、しかるべきときに $j$ へ $-1$ が代入 (j = next[0];) されます。
$j$ がひとたび $-1$ になったらすぐに while を抜けるように (j >= 0) しておきましょう。
例として txt = "abbaba", pat = "aba" のとき、プログラムの動作をトレースしてみます。
序盤は省略しますが、$i = 2, j = 2 $ になってはじめて内側の while 文の中身が実行されます。
以下は txt[2] != pat[2] を示した図です。
abbaba abx
$\mathrm{next}[2] = 0$ なので j = next[j]; によって $j$ に $0$ が代入されます。
さらに txt[2] != pat[0] なのでもう一度 j = next[j]; が実行され、$j$ に $-1$ が代入されて while を抜けます。
while を抜けたあと $i, j$ はインクリメントされ、$i = 3, j = 0$ になっています。
以下は、次回のループで txt[3] と pat[0] が比較される予定を示した図です。
abbaba _
残るはパターン文字列 pat から $\mathrm{next}[]$ 配列を生成する build_next 関数の実装です。
とは言っても、kmp_search 関数とほぼ同じ見た目になります。パターン自身と照合させるイメージです。
$i$ の小さい順に $\mathrm{next}[i]$ を順次確定させていきます。
$i = 0$ については $\mathrm{next}[0] = -1$ とするのでした。
また、つねに $\mathrm{next}[1] = 0$ が成り立ちます。
長さ $1$ の文字列において全体と一致しない prefix (および suffix) は空文字列のみだからです。
$\mathrm{next}[i]$ は最大でも $i - 1$ にしかならないのでその範囲を全てチェックすれば確実に $\mathrm{next}[i]$ を求めることができます。
しかし、さらに考えると $\mathrm{next}[i]$ は $\mathrm{next}[i - 1]$ から最大でも $+1$ しかされないことが分かります。
これは前述のように、文字列の一致についてstep by step な構造があるからです。
つまり、$\mathrm{next}[i] = \mathrm{next}[i - 1] + 1$ となるのは、パターンの $i - 1$ 番目の文字と $\mathrm{next}[i - 1]$ 番目の文字とが一致するときに限ります。
それぞれの文字は「パターンの先頭 $i$ 文字を切り出した文字列」における長さ $\mathrm{next}[i]$ 文字の suffix の末尾、prefix の末尾です。
たとえば pat = "ababaabb" とします。
このとき $\mathrm{next}[5] = \mathrm{next}[4] + 1 = 3$ でした。
この値が確定する直前の様子は次のように表せます。配列の添字が $0$ 始まりであることに注意してください。
ababa ab_
次に $\mathrm{next}[i]$ が $\mathrm{next}[i - 1]$ から増加しない場合を考えましょう。
これはちょうど次のような状況です。注目している位置以降は . で表しています。
ababaa abab..
「パターンの先頭 $6$ 文字を切り出した文字列」において、末尾 $4$ 文字と先頭 $4$ 文字が一致していません。
しかし、一歩手前では "aba" (先頭 $5$ 文字からなる文字列における長さ $\mathrm{next}[5] = 3$ の prefix = suffix) が一致していたわけですから、これを利用しましょう。
"aba" はパターンの先頭 $3$ 文字を切り出した文字列とも考えられ、$\mathrm{next}[3]$ がすでに求まっており、その値は $1$ です。
したがって、"aba" の先頭 $1$ 文字と末尾 $1$ 文字は一致していて、これは "ababa" (パターンの先頭 $5$ 文字を切り出した文字列) に対しても成り立ちます。
そこでパターンの $5$ 番目の文字 pat[5] と $\mathrm{next}[\mathrm{next}[5]]$ 番目の文字 pat[1] を比べます。
これらが等しければ $\mathrm{next}[6] = \mathrm{next}[\mathrm{next}[5]] + 1$ と確定できます。
しかし以下の図で見るように pat[5] = 'a', pat[1] = 'b' であり、異なる文字です。
ababaa
abab..
ab....
そうすると、次は "a" をパターンの先頭 $\mathrm{next}[\mathrm{next}[5]] = 1$ 文字を切り出した文字列とみなして、同様の手順を実行します。
$\mathrm{next}[1] = 0$ が分かっているので、pat[5] と pat[0] を比べればいいです。
そして、この比較は成功します。
ababaa
abab..
ab....
a.....
最終的に $\mathrm{pat}[6] = 0 + 1$ が確定します。
$+1$ は注目している文字が一致した分で、$0$ はその文字より左で一致している長さの分です。
build_next 関数の実装例を以下に示します。
vector<int> build_next(const string &pat) { vector<int> next(pat.size() + 1); int i = 0, j = -1; next[i] = j; while (i < pat.size()) { while (j >= 0 and pat[j] != pat[i]) { j = next[j]; } i += 1; j += 1; next[i] = j; } return next; }
kmp_search ではテキストとパターンの先頭同士から比較を開始していましたが、こちらでは $1$ 文字ずらして始めないといけません。
文字列全体を prefix (suffix) とみなさないためです。
したがって、下図のように pat[0] と pat[1] の比較から始めます。
ababaabb _
内側の while を抜けた直後は、
pat[j] == pat[i]pat[j - 1] == pat[i - 1]- ...
pat[0] == pat[i - j]
が満たされています。
つまり、「パターンの先頭 $i + 1$ 文字を切り出した文字列」において長さ $j + 1$ の prefix と suffix は一致しています。
pat[0] から pat[i] までには $i + 1$ 文字存在することに注意してください。
最後に kmp_search の計算量を考えます。
ループの最も内側の j = next[j]; が関数全体で実行される回数 $n$ を評価すればいいです。
$j$ の増減に注目すると、はじめ $j = 0$ で、j += 1; が実行されると $1$ 増え、j = next[j]; が実行されると $1$ 以上減ります ($\mathrm{next}[j] < j$ だからです) 。
そして外側の while を抜けた時点で $j$ は $0$ 以上です。
外側のループは最大 $N$ 回 (テキストの長さと同じ回数) 回るので、少なくとも $n \le N$ でないといけません。
したがって kmp_search 関数の計算量は $O(N)$ と分かりました。
build_init 関数についても同様の解析によって $O(M)$ であることが分かります。
よって、KMP法全体での計算量は $O(N + M)$ です。
