Philosophical … Balance

Some power influenced Rikka to stand LCR up. Is it a coincidence that LCR brought her to the middle school attached to the EC Final host?

Rikka is trying to enter the NWPU, but the guard who has been possessed by the devil doesn't let her in. Now she has an idea of forging a pass.

The key is the pass ID, a special string for access-handshaking. The guard has a string s of length n as the secret key; when he checks a pass, he chooses a suffix of it (that is, a substring containing the last character), and calculates the length l of the longest common prefix of the pass ID and the suffix. l is proportion to the probability to let her pass.

Now Rikka has got the secret key in some secret way. She wants to choose a suffix as the pass ID, too. Since the suffix which the guard will choose is unknown, Rikka would choose her pass ID randomly. That is, Rikka would design a probability distribution for the suffixes (i.e. a series of real numbers $\{p_i\}, i = 1, 2, \dots , n$ , such that $p_i \ge 0, \sum_{i=1}^n p_i = 1$ , which means she would choose the suffix of length i, denoted by $s_i$ , with a probability of $p_i$ ), and maximize the minimum mathematical expectation of l for any suffix the guard chooses.

Could you please calculate the maximum value of the minimum mathematical expectation of l? Precisely speaking, what you should calculate is $\max_{\{p_i\}} \left(\min_{j=1}^n\left(\sum_{k=1}^n p_k \mathrm{lcp}(s_k,s_j)\right)\right),$ where $\mathrm{lcp}(s_k,s_j)$ means the length of longest common prefix of $s_k$ and $s_j$ .

The first line contains one integer $T~(1 \leq T \leq 10^5)$ , the number of test cases. Then T test cases follow.

Each test case contains a string s of length $n~(1 \leq n \leq 2 \times 10^5)$ , consisting of only lowercase letters, the secret key.

It is guaranteed that the sum of n in all test cases is at most $5 \times 10^5$ .

#include<bits/stdc++.h> using namespace std; typedef long double ld; const int maxn=1000000; char s[maxn+10]; int n,t; namespace sam { const int maxc=maxn*2; ld f[maxc+10]; int ch[maxc+10][26],fa[maxc+10],maxl[maxc+10],np=1,ndcnt=1; bool is[maxc+10]; vector<int> g[maxc+10]; void init() { for(int i=1;i<=ndcnt;++i) { memset(ch[i],0,sizeof ch[i]); fa[i]=maxl[i]=is[i]=0; f[i]=0; g[i].clear(); } np=ndcnt=1; } void add(int c) { int p=np; np=++ndcnt; maxl[np]=maxl[p]+1; is[np]=1; for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np; if(p) { int q=ch[p][c]; if(maxl[p]+1==maxl[q]) fa[np]=q; else { int nq=++ndcnt; fa[nq]=fa[q]; fa[q]=fa[np]=nq; maxl[nq]=maxl[p]+1; for(int i=0;i<26;++i) ch[nq][i]=ch[q][i]; for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq; } } else fa[np]=1; } void dfs(int p) { if(is[p]) { f[p]=maxl[p]; return; } ld sum=0; for(int i=0;i<(int)g[p].size();++i) { int e=g[p][i]; dfs(e); sum+=1./(f[e]-maxl[p]); } int c=g[p][0]; f[p]=maxl[p]+1./(f[c]-maxl[p])/sum*(f[c]-maxl[p]); } void build() { for(int i=2;i<=ndcnt;++i) g[fa[i]].push_back(i); dfs(1); } } int main() { scanf("%d",&t); while(t--) { sam::init(); scanf("%s",s+1); n=strlen(s+1); reverse(s+1,s+n+1); for(int i=1;i<=n;++i) sam::add(s[i]-'a'); sam::build(); printf("%.10Lf\n",sam::f[1]); } }

详情