51nod 1292 字符串中的最大值V2（后缀自动机）

时间：2022-07-23 21:50:02

题意：

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

题解：

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

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

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 1e6 + ;

const int maxn2 = maxn*;

int cnt = , last = ;

int endpos[maxn2], tr[maxn2][], par[maxn2], mx[maxn2], c[maxn2], id[maxn2];

int n;

char s[maxn];

void extend(int x){

    int np = ++cnt, p = last;

    endpos[np] = ;

    mx[np] = mx[p] + ; last = np;

    while(p && !tr[p][x]) tr[p][x] = np, p = par[p];

    if(!p) par[np] = ;

    else {

        int q = tr[p][x];

        if(mx[q] == mx[p]+) par[np] = q;

        else {

            int nq = ++cnt; mx[nq] = mx[p]+;

            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 = ; i <= cnt; i++) c[mx[i]]++;

    for(int i = ; i <= n; i++) c[i] += c[i-];

    for(int i = ; 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 = ; i < n; i++) extend(s[i]-'a');

    topsort();

    endpos[] = ;

    long long ans = ;

    for(int i = ; i <= cnt; i++){

        ans = max(ans, (long long)endpos[i]*mx[i]);

    }

    cout<<ans<<endl;

    return ;

}

相关文章