天津做网站外包公司有哪些,免费空间网站怎么做出来的,信息网站开发合同,别墅装修排名题意#xff1a;给定字符串#xff0c;求所有前缀的最小后缀。 n≤2107n\leq 2\times10^7n≤2107
最小后缀就是Lyndon分解的最后一段。而Duval本质上是可以重复修改的增量算法#xff0c;所以是可以做的。
记ansians_iansi为前缀iii的最小后缀。设维护未确定的循环节的指…题意给定字符串求所有前缀的最小后缀。
n≤2×107n\leq 2\times10^7n≤2×107
最小后缀就是Lyndon分解的最后一段。而Duval本质上是可以重复修改的增量算法所以是可以做的。
记ansians_iansi为前缀iii的最小后缀。设维护未确定的循环节的指针为i,j,ki,j,ki,j,k即Si...k−1tt...tt1S_{i...k-1}tt...tt_1Si...k−1tt...tt1其中ttt为Lyndon Word,t1t_1t1为其可空前缀jk−∣t∣jk-|t|jk−∣t∣
当SjSkS_jS_kSjSk时根据意识流前缀jjj的最小后缀一定在[i,j][i,j][i,j]内。因为是个循环所以anskansjk−jans_kans_jk-janskansjk−j
当SjSkS_jS_kSjSk令jijiji此时Sj...kS_{j...k}Sj...k是个Lyndon Word所以anskjans_kjanskj
当SjSkS_jS_kSjSk相当于t1t_1t1这一段的ansansans都是假的需要重新计算不用管。但∣t1∣1|t_1|1∣t1∣1的时候会出一些奇怪的问题需要把anskans_kansk的值算出来为iii或kkk。
复杂度O(n)O(n)O(n)
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 20000005
using namespace std;
char s[MAXN];
int ans[MAXN];
const int MOD1e97;
int main()
{int T;scanf(%d,T);while (T--){scanf(%s,s1);int nstrlen(s1);for (int i1;in;i) ans[i]0;ans[1]1;for (int i1;in;){int ji,ki1;ans[k]k;while (s[j]s[k]){if (s[j]s[k]) ans[k]ans[j]k-j,j;else ans[k]ji;k;}while (ij) ik-j;ans[k]i;}
// for (int i1;in;i) printf(%d%c,ans[i], \n[in]);int sum0;for (int i1,x1;in;i,xx*1112ll%MOD) sum(sum1ll*ans[i]*x)%MOD;printf(%d\n,sum);}return 0;
}
