我觉得很厉害。因为这道字符串题目的分析非常自然而且并不复杂。

考虑枚举右端点到$r$时，维护可能成为答案的位置的集合。显然对于相邻两个元素$i,j$，我们有$\text{lcp(S[i:],S[j:])}>r-j$，否则可以删去$i,j$其中之一。画图不难发现我们只需要保证对于任意$k$，满足$\text{lcp(S[i:],S[k:])}>r-k$，也就是只用和第一个位置进行比对。注意$\text{lcp}$的长度是不随右端点$r$变化的，可以看成常数。

当然，上述分析并不能导向一个正确的解法。假设我们已经维护出来了上述集合，有一个非常套路的想法，假设已经检查完了$i$之前的所有位置，那么对于之后的一个位置$j$，假设$j-i<r-j$，那么不难发现$S[i:j)=S[j:2j-i)$，我们记这一段为$A$（更确切地说$A$是$S[i:r]$的周期），$2j-i$以后的为$B$，那么我们得到$A+A+B,A+B+A,B+A+A$三种方案。容易观察出中间那种肯定是不优的，也就是$j$一定不优。那么有$2j\ge r+i$，显然只有最多$\log$个需要检查，这道题就做完了。因为$\text{lcp}$已经匹配到了底所以用$z$函数辅助检查一下即可。

复杂度$O(n\log n)$。

代码咕了。其实是我不会打$z$函数

至于维护集合那个部分，可以自己编一个做法，事实上发现每次暴力重构就完了。

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N=3e6+5;
int n,z[N],res;
string s;
vector<int>f,g;
int solve(int pos1,int pos2,int last){if(pos1==-1)return 1;pos1+=last-pos2+1;if(z[pos1]<last-pos1+1){return s[z[pos1]]<s[pos1+z[pos1]];}pos1=last-pos1+1;if(pos1+z[pos1]>=pos2)return 0;return s[z[pos1]]>s[pos1+z[pos1]];
}
void ins(int pos,int last){while(g.size()&&s[g.back()+last-pos]!=s[last]){if(s[g.back()+last-pos]<s[last])return;g.pop_back();}if(!g.size()||2*pos>=last+g.back()){g.pb(pos);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s,n=s.size();for(int i=1,l=0,r=0;i<n;i++){if(r>=i&&z[i-l]<r-i+1)z[i]=z[i-l];else{z[i]=max(0,r-i+1);while(i+z[i]<n&&s[i+z[i]]==s[z[i]])z[i]++;}if(i+z[i]-1>r)l=i,r=i+z[i]-1;}for(int i=0;i<n;i++){g.clear(),res=-1;for(auto x:f)ins(x,i);ins(i,i),f=g;for(auto x:g){if(solve(res,x,i))res=x;}cout<<res+1<<" ";}
}