这是我给我们队本场比赛的唯一贡献，而且还带着 3 发罚时 /kk。
考虑一个字符串的最长后缀怎么求，显然一个后缀排序就完事了，可是这并不能拓展到一个字符串的所有前缀，所以他 GG 了。
所以考虑 lyndon 分解，那么最小后缀就是分解得到的最后一个 lyndon word 。证明略
所以要计算出字符串的所有前缀的 lyndon 分解，考虑 Duval 算法的过程，设当前前缀的末尾是 (j)
- 如果 (j) 是原串 lyndon 分解的一段终点，那么他的答案就是这段的起点
- 否则，设当前维护的近似 lyndon 串的长度为 (len) ，最小周期为 (d)
-
- 若 (len=d) ，则 (ans_j=j-len) ，即当前的近似 lyndon 串是前缀 ([1...j]) 分解得到的最后一个 lyndon word
- 否则 (ans_j=ans_{j-d}+d) ，即与上一个周期答案相对位置相同，证明：显然不会有这个周期之前的答案优于他，否则他就应该被前一个 lyndon word 包含；所以只与最后一个周期有关，必然是这样。
题外话：lyndon 分解那套理论真的是 easy 吗
Code：
#define N 1000005
char s[N];
int ans[N],tans[N];
void work()
{
scanf("%s",s+1);
int n=strlen(s+1);
int cnt=0;
for(int i=1;i<=n;)
{
int j=i+1,k=i;
ans[i]=i;
while(j<=n&&s[k]<=s[j])
{
if(k==i) ans[j-1]=i;
else ans[j-1]=ans[k-1]+(j-k);
if(s[k]==s[j]) k++;
else k=i;
j++;
}
while(i<=k)
{
i+=j-k;
tans[++cnt]=i-1;
}
}
for(int i=1;i<=cnt;i++) ans[tans[i]]=tans[i-1]+1;
int Ans=0,tmp=1;
for(int i=1;i<=n;i++)
{
Ans=add(Ans,mul(tmp,ans[i]));
tmp=mul(tmp,1112);
}
printf("%d
",Ans);
}
signed main()
{
int T=read(); while(T--) work();
return 0;
}