先来说个暴力
从前往后枚举\(k=i(i=1,2,...,n)\)
维护一个集合\(S\)，令\(x=max\{S\}\)，使得在前缀\(k\)下，所有集合中的元素\(k-x+1\)的前缀都相同，也就是说在还未移位时是分不出大小关系的
用exkmp加速可以\(O(1)\)比较
然后发现这样过了，下面证明时间复杂度。
考虑\(i<j\)，比较不出大小，即\(lcp(S_i,S_j)\ge k-j+1\)
若\(k-j+1\ge j-i\)，即前缀\(k\)形如\(ABBC\)，\(C\)是\(B\)的前缀，\(S_i=BBC|A\)，\(S_j=BC|AB\)，\(S_{2i-j}=C|ABB\)。若\(BCA\le CAB\)，有\(S_i\le S_j\le S_{2i-j}\)；若\(BCA\ge CAB\)，有\(S_i\ge S_j\ge S_{2i-j}\)，因此\(S_j\)也可以丢掉了
所以保留下来的点集大小\(O(nlogn)\)
原文：https://www.cnblogs.com/Grice/p/12682287.html