题意

求字符串所有前缀的所有后缀表示中字典序最小的位置集合，最终转换为1112进制表示。比如aab，有三个前缀分别为a，aa，aab。其中a的后缀只有一个a，位置下标1；aa有两个后缀，字典序最小的是a，下标为2；aab有三个后缀，字典序最小的是aab，下标是1。答案为 \(1*(1112)^2+2*(1112)^1+1*(1112)^0\)

字符串长度1e6

分析

在求字符串的最小表示法中，有一个叫做Lyndon分解的求法，Lyndon分解可以使用Duval算法。详情可以参考 oi-wiki。

设\(d[j]\) 为前缀 j 的字典序最小后缀的起始位置，i, j, k 指针与oi-wiki中介绍的一致。对于下面三种情况讨论d[j]的求解

\(j - k\) 为 近似Lyndon串前缀的循环节长度。

1. \(s[j] == s[k]\), 那么d[j] = d[k] + (j - k); 本质上是取了 j 所在循环节的开头位置。(\(s=www\overline{w}\) 中 \(\overline{w}\) 的开头)

2. \(s[j] > s[k]\)，那么 d[j] = i; 当前\(s[i..j]\) 是一个Lyndon串，所以d[j] = i;

3. \(s[j] < s[k]\)，Duval算法中会重新处理 j 所在的这一段(\(s=www\overline{w}\) 中 \(\overline{w}\)), i会被置为这一段的开头，继续后面的分解过程。这里有一个特殊情况需要考虑，如果 \(j == k + 1\)，那么 j 就是下一次分解的开头, i 会被置为 j，所以要手动将d[j] = j。

   #include

   using namespace std;
   typedef long long ll;
   const int inf = 0x3f3f3f3f;
   #define dbg(x…) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
   void err() { cout << "\033[39;0m" << endl; } template void err(const T& arg,const Ts&… args) { cout << arg << " "; err(args…); }
   const int N = 1e6 + 5;
   const int mod = 1e9 + 7;
   char s[N];
   ll d[N], n;

   int main(){
   int T;scanf("%d", &T);
   while(T--){
   scanf("%s", s + 1);
   n = strlen(s + 1);
   int i = 1; d[1] = 1;
   while(i <= n) { int j = i + 1, k = i; while(j <= n && s[k] <= s[j]) { if(s[k] == s[j]){ d[j] = d[k] + (j - k); k ++; } else { d[j] = i; k = i; } j ++; } d[j] = j; // 当 k == j - 1 时，必须有这一条。因为下面的循环结束后，i = k + 1 也就是 j，接下来的大循环不会在处理当前的 j， 这次 j 是被当做lyndon分解串的一个起点对待的。 while(i <= k) i += j - k; } ll res = 0; for(int i = n;i>=1; i --){
   res = res * 1112 + d[i];
   res %= mod;
   }
   printf("%lld\n", res);
   }
   return 0;
   }