本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
学习完lyndon分解后，我们发现这个分解可以分割字符串并且分割成a[i]>=a[i+1]且每个字符串都是自己的最小后缀
因此在分解的过程中
当遇到s[j]==s[k]，这说明前面都是循环的字符串，那么答案就是上一个同样位置的答案后移一个循环节长度
如果s[j]<s[k]，这说明马上整串都变成一个lyndon字符串了，因此答案就是开头位置是最小的。
如果s[j]>s[k]那就说明当前循环节的答案是错误的，不过因为本身在求lyndon字符串的时候，指针就会跳转到当前循环节首位，所以只需要重算一遍就行了
注意初始化，因为刚开始只有一个字符，因此答案是自身
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
const int mod=1e9+7;
const int BAS=1112;
string s;
int p[N];
int f[N];
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
f[0]=1;
for(int i=1;i<N;++i) f[i]=1LL*f[i-1]*BAS%mod;
while(t--){
string s;
cin>>s;
int n=(int)s.size();
s=" "+s;
for(int i=1;i<=n;){
int j=i,k=i+1;
p[i]=i;
while(k<=n&&s[j]<=s[k]){
if(s[j]<s[k]){
p[k]=i;
j=i;
}
else{
p[k]=p[j]+(k-j);
j++;
}
k++;
}
while(i<=j){
i+=k-j;
}
}
ll ans=0;
for(int i=1;i<=n;++i)
ans=(ans+1ll*f[i-1]*(p[i]))%mod;
cout<<ans<<endl;
}
}
View Code
