HDU.6761.Minimum Index(Lyndon分解)

题目大意：给一个字符串，求字符串的所有前缀的最小后缀；

思路：主要还是要理解Lyndon串的算法的整一个过程

 参考：搬运来自

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) #define pb push_back using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=1e9+7; const ll N =2e6+10; const ll M =250000; const double eps = 1e-4; //const double pi=acos(-1); ll qk(ll a,ll b){ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b/=2;}return ans%mod;} int n; int d[N]; char s[N]; void sovle(){cin>>(s+1);n=strlen(s+1);int i=1;d[1]=1;ll ans=0;while(i<=n){int j=i,k=i+1;while(k<=n&&s[j]<=s[k]){if(s[j]==s[k]) d[k]=d[j]+(k-j),j++;else {d[k]=i;j=i;}k++;}d[k]=k;while(i<=j) i+=k-j;}for(int i=n;i>=1;i--) ans=(ans*1112%mod+d[i])%mod;cout<<ans<<endl; } int main() { #ifdef LOCALfreopen("in.txt", "r", stdin); #elseiosint t=1;cin>>t;while(t--) sovle(); #endif // LOCALreturn 0; }

总结

以上是生活随笔为你收集整理的HDU.6761.Minimum Index(Lyndon分解)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。