Hdu 6761 Minimum Index —— Lyndon分解，小小的DP思想？

本文主要是介绍Hdu 6761 Minimum Index —— Lyndon分解，小小的DP思想？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

i从1到n，问你所有字符串s[1]…s[i]的字典序最小的后缀的起点是什么。

题解：

其实还是满简单的把，就是用到了Lyndon分解的一点原理。
那么假设已经会了Lyndon分解
我们现在对于每一个位置，都知道了这个Lyndon串的开头，那么如果s[j]==s[k]的话，就说明在循环中，注意这个时候不能直接就等于这个循环的开头，会出现以下情况：（之后默认起始位置为0）
aabcaabd
位置5的话，Lyndon循环的开头就是4，但是位置5的最小字典序后缀就是它本身，为什么会出错？是因为你只注意了Lyndon串的循环，但是没注意到每个循环内部的情况，这时候可以用KMP去做，BUT，我拒绝。
我们可以发现，第一个循环的情况一定是正确的，因为它在作为第一个Lyndon分解的时候，它照顾到了自己内部的情况。
那么我们后面循环的位置就可以从前面的推过来：sta[k]=sta[j]+k-j。
那这个时候就有人说了，啊为什么直接复值啊，如果当前的循环是独立的Lyndon呢，比如说abcabb，那不是就错了吗。
但是我们注意到，后面的串作为新的Lyndon分解的时候，我们会对后面的串重新做一遍。提问的人一定是没理解这个算法。
然后第二种情况就是s[j]<s[k]，那么所有循环作为一个Lyndon串，因此sta[k]=i。
最后就是s[j]>s[k]，此时我们就开始下一个Lyndon分解，然后赋值sta[i]=i即可。

最后只需要计算一下答案就结束了，是不是非常的敢单呢。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
const ll mod=1e9+7,sed=1112;
char s[N];
vector<int>pos;
int sta[N];
ll Lyndon(char *s){pos.clear();ll ret=1;int n=strlen(s);for(int i=0;i<n;){int j=i,k=i+1;sta[i]=i;while(k<n&&s[j]<=s[k]){if(s[j]==s[k])sta[k]=sta[j]+k-j,j++;else sta[k]=j=i;k++;}while(i<=j){i+=k-j;}}ll ans=0;for(int i=0;i<n;i++)ans=(ans+ret*(sta[i]+1))%mod,ret=ret*sed%mod;return ans;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%s",s);printf("%lld\n",Lyndon(s));}return 0;
}
/*
1
aabcaabd*/