$lyndon\ word$（以下简写为Lw）：对于一个字符串s，其为Lw当且仅当其的最小后缀为自身

性质：若$u<v$为LW，那么$uv$也为Lw（反证法即可证）

$lyndon$分解：将一个字符串分为$s=s_{1}s_{2}…s_{k}$，满足$\forall 1\le i\le k$，有$s_{i}$为Lw；$\forall 1\le i<k$，有$s_{i}\ge s_{i+1}$

性质：对于一个字符串，有且仅有1个$lyndon$分解

存在性：初始将令$s_{i}=s[i]$（显然都为Lw），然后重复以下过程：若存在$s_{i}<s_{i+1}$，任选其中一个i将两个串合并，根据Lw的性质其仍为Lw，由于每一次合并都会减少一个字符串，因此合并次数有限，当其停止时即符合要求

唯一性：1.任意一组解都可以用上述方式构造出（证明略）；2.对于三个字符串$s_{1}<s_{2}<s_{3}$暴力枚举所有合并方法，容易证明只有1种

记$f(i)$表示以i为开头的$lyndon$分解所拓展到的位置，考虑如何去求$f(f(…f(1)+1)+1)$

有一种做法：不断将i与之后的字符合并，这显然是不够的（比如$aab$，a无法与a合并但能与$ab$合并），但从中我们可以想到1种做法：当$i$合并到$j$后发现无法合并下去，那么不妨去拓展$j$，直到拓展到一个位置$k$并发现满足$s[i,j)<s[j,k]$时，就可以令$f(i)=k$并继续拓展$i$（由于$s[i,j)<s[j,k]$，所以如果j可以拓展，那么i一定也可以拓展），而如果直到j拓展完都没有满足，那么$f(i)=j$并已经求出了$f(j)$

考虑这种做法的时间复杂度：一个字符最多只会被拓展一次，因此复杂度为$o(n)$

PS：这种做法就是Duval算法，不同的是Duval算法在发现了$s[i,j)>s[j,k]+zzz…$（出现了不同的位置）时会直接令$f(i)=j-1$并去求$f(j)$

回到原题，容易发现第i个点的最小后缀就是以i为结尾最长的Lw，那么只需要当拓展到i时记录一下即可

1 #include
2 using namespace std;
3 #define N 1000005
4 #define mod 1000000007
5 int t,a[N];
6 char s[N];
7 int main(){
8 scanf("%d",&t);
9 while (t--){
10 scanf("%s",s);
11 int n=strlen(s);
12 for(int i=0;i<n;){
13 int j=i+1,k=i;
14 a[i]=i;
15 while ((j<n)&&(s[k]<=s[j])){
16 if (k==i)a[j-1]=i;
17 else a[j-1]=a[k-1]+j-k;
18 if (s[k]==s[j])k++;
19 else k=i;
20 j++;
21 }
22 while (i<=k){
23 a[i+j-k-1]=i;
24 i+=j-k;
25 }
26 }
27 int s=1,ans=0;
28 for(int i=0;i<n;i++){
29 ans=(ans+s*(a[i]+1LL))%mod;
30 s=s*1112LL%mod;
31 }
32 printf("%d\n",ans);
33 }
34 }