题意：

有一个字符串T。字符串S的F函数值可以如下计算：F(S) = L * S在T中出现的次数（L为字符串S的长度）。求所有T的子串S中，函数F(S)的最大值。

 

题解：

求T的后缀自动机，然后所有每个后缀自动机的结点u

求出endpos[u]*maxlen[u]中的最大值即可

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 1e6 + 100;const int maxn2 = maxn*2;int cnt = 1, last = 1;int endpos[maxn2], tr[maxn2][30], par[maxn2], mx[maxn2], c[maxn2], id[maxn2];int n;char s[maxn];void extend(int x){    int np = ++cnt, p = last;    endpos[np] = 1;    mx[np] = mx[p] + 1; last = np;    while(p && !tr[p][x]) tr[p][x] = np, p = par[p];    if(!p) par[np] = 1;    else {        int q = tr[p][x];        if(mx[q] == mx[p]+1) par[np] = q;        else {            int nq = ++cnt; mx[nq] = mx[p]+1;            memcpy(tr[nq], tr[q], sizeof(tr[q]));            par[nq] = par[q]; par[q] = par[np] = nq;            while(p && tr[p][x] == q) tr[p][x] = nq, p = par[p];        }    }}void topsort(){    for(int i = 1; i <= cnt; i++) c[mx[i]]++;    for(int i = 1; i <= n; i++) c[i] += c[i-1];    for(int i = 1; i <= cnt; i++) id[c[mx[i]]--] = i;    for(int i = cnt; i; i--) endpos[par[id[i]]] += endpos[id[i]];}int main(){    cin>>s;    n = strlen(s);    for(int i = 0; i < n; i++) extend(s[i]-'a');    topsort();    endpos[0] = 0;    long long ans = 0;    for(int i = 1; i <= cnt; i++){        ans = max(ans, (long long)endpos[i]*mx[i]);    }    cout<
        
         <