(より詳しい解説は後日ブログで公開します)

\(f\) を求める正しい実装 (Morris–Pratt 法) は for (; j >= 0 && s[j] == s[i]; j = g[j]) {} の == を != にしたものです．

実は，任意の文字列 \(s\) に対し，\(i \ge 1\) のとき \(f(s, i+1) \ne g(s, i+1)\) です．これは上の for 文の終了前後を考えるとわかります：

• \(f(s, i+1) = g(s, i+1) \ge 1\) とすると，for 文を抜けたときの比較結果が \(s[f(s, i+1) - 1] = s[i]\) かつ \(s[g(s, i+1) - 1] \ne s[i]\) となり矛盾．
• \(f(s, i+1) = g(s, i+1) = 0\) とすると，\(i \ge 1\) より \(j = -1\) の直前は必ず \(j = 0\) なので，そのときの比較結果が \(s[0] \ne s[i]\) かつ \(s[0] = s[i]\) となり矛盾．

このことから，\(\displaystyle\sum_{k=0}^n \bigl\lvert f(s,k) - g(s,k) \bigr\rvert \ge n-1\) です．

最小値 \(n-1 = A+B-1\) は例えば次のように達成できます．\(A \le B\) としてよく，ab を \(1\) 個，b を \(B-A\) 個，ab を \(A-1\) 個この順に連結させると，\(A < B\) なら，\(f\) が \((-1, 0, \underbrace{0,\ldots,0}_{B-A+1}, 1,2,\ldots,1,2)\)，\(g\) が \((-1, 0, \underbrace{1,\ldots,1}_{B-A+1}, 2,1,\ldots,2,1)\) となり，\(A = B\) なら \(f\) が \((-1,0,0,1,\ldots,A+B-2)\)，\(g\) が \((-1, 0,1,2,\ldots,A+B-1)\) となることが確認できます．