Runの列挙 (Main-Lorentz algorithm) - 迷いませんか？

Main-Lorentz Algorithm 概要 文字列のrunをで列挙することができるアルゴリズム runは文字列内に現れる部分文字列の繰り返しのことで、特に長さが極大で周期が最小のものを指すっぽい 情報としては区間と周期を持ち、実際に使うときは(l, r, period)としてs[l, r)の周期がperiodみたいに持つ 注意するべきなのは、繰り返しはピッタリである必要はなくて(r - l) % period != 0でもよい ただしr - l >= 2*periodであるもののみを考える 例 "mississippi" 区間: [1, 8), period: 3 長さ3の"iss"が7/3周期分ある s[0] != s[0+period(= 3)] かつ s[8] != s[8-period(= 5)]だからこれ以上伸ばせなくて長さが極大である あとは周期1で2周期分のやつが3つ