文字列に含まれる連の最大数について

繰り返し構造とは文字列処理の中でも最も基本的な概念の一つであり，数多くのアルゴリズムに応用がなされています．
なかでも連(runs)とは，左右に周期性が拡張不可能であるような2回以上の繰り返し文字列のことをいいます．

KolpakovとKucherovは長さnの文字列に含まれる連の最大数RUNS(n)がO(n)であることを示しました．この事実をもとに，文字列に含まれるすべての連を求めるアルゴリズムが線形時間で動作することを証明しました．さらに彼らはRUNS(n) < nであることを予想しました．これを連予想(runs conjecture)といいます．

さらに組み合わせ論での興味から，RUNS(n)の上限と下限をより詳しく解明する研究が数多くなされています．

上限

• 5n [Rytter]
• 3.48n [Puglish]
• 3.44n [Rytter]
• 1.6n [Crochemore]
• 1.024n [Crochemore][Baturo]

下限

• 0.927n [Franek]
• 0.944n [Matsubara]
• 0.944575n [Matsubara(予想)][Simpson]

すなわち，これまでの研究により，
0.944575n < RUNS(n) < 1.024n
であることがわかっています．
しかし，連予想が正しいのかどうかは未だに解明されていません．