>>488
過半数に達したかどうか分かるのは最低でも全体の半分は検査が終わってる時点（aしか出現してないなど)
過半数判定そのものが１ループのコストより遥かに小さいものでないと速くならないが
実際は過半数判定がそれなりにコストのかかるものなので、過半数判定が無いものより高コストになるだけ

文字列検査の１ループは ループ処理のコスト[A]　＋　１文字判定・カウントのコスト[B]　＋　カウントが過半数に達したかの判定のコスト[C]

過半数判定なしは n×([A]+[B]) (文字列の最後まで検査)
過半数判定ありは m×([A]+[B]+[C]) (n/2 < m <= n)

過半数判定は前半部n/2では必要ないからループを前半部と後半部の２回に分けて
過半数判定ありは (n/2)×([A]+[B]) + m'×([A]+[B]+[C]) (0< m' < n/2)
とも出来るけど

m'×([A]+[B]+[C]) < (n/2)×([A]+[B]) になる確率はそんなに高くなさそうな気がするが

[A]はコスト 3 くらいか、[B]もコスト 3 くらい、[C]はコスト 2　くらいだとしたら
m'×8 < (n/2)×6 となるから m' < (3/4)×(n/2) ・・・ これは何なのか自分でも分からなくなった