Main-Lorentz algorithm メモ

文字列Sのrun

s[i,...,j] であって、区間長の半分以下の周期を含み、左or右に一つ伸ばせないもの

長さaのrunはO(|S| log a)で列挙できる

全てのrunの個数はO(|S|)

 

文字列Sに含まれる全てのrunO(|S| log |S|)で列挙する

www.sciencedirect.com

Finding repetitions - Competitive Programming Algorithms

https://tenka1.klab.jp/2014/explain/final_e.pdf